Understanding Lists: Array and Linked List Implementations

목록은 중복 가능성이 있는 주문 컬렉션을 효율적으로 관리하기 위한 필수 데이터 구조입니다.

### ADT의 목록 이해하기: 배열 목록 및 연결된 목록
* 📚 이 동영상을 보고 나면 **추상 데이터 유형(ADT)의 리스트 개념**과 EST에서 **배열 리스트와 링크된 리스트의 구현**을 이해할 수 있습니다.
* 🔍 목록은 값을 저장하는 데 사용되는 추상 데이터 유형으로, **정렬된 특성과 중복**을 허용하는 것이 특징입니다.
* 📝 목록은 순서와 중복 가능성이 중요한 **객관식 문제의 답안 저장**과 같은 시나리오에서 특히 유용할 수 있습니다.
* 📊 예를 들어, **객관식 문제 200개**를 관리할 때 리스트를 사용하면 문제 특성상 중복되는 답을 순서대로 저장하고 효율적으로 관리할 수 있습니다.
* 📈 목록은 **2021 스택 오버플로 설문조사 결과**와 같이 순위가 중복되지 않더라도 순서가 중요한 프로그래밍 언어의 순위를 저장하는 데에도 적용할 수 있습니다.
* 🛠 목록을 구현할 때 저장소로 배열을 사용하는 **배열 목록**과 포인터로 연결된 노드로 구성된 **링크된 목록**의 두 가지 기본 유형이 인식됩니다.
* 🔗 배열 목록에서 요소는 인접한 메모리 위치에 저장되는 반면, **링크된 목록은 각 노드가 다음 노드를 가리키는 비연속적 저장**을 허용하여 메모리 사용의 유연성을 제공합니다.
* 이러한 구현과 추가, 삽입, 검색과 같은 작업을 이해하면 **프로그래밍 기술과 데이터 관리 능력**이 향상됩니다.

### 연결된 목록 이해하기 작업, 비교 및 인사이트
* 🔗 연결된 목록에서 **10과 12와 같은 값을 추가**하려면 새 노드를 만들고 그에 따라 머리와 꼬리에 대한 포인터를 업데이트해야 합니다.
* 📈 get` 함수를 사용하여 값을 검색할 때, 원하는 인덱스에 도달하기 위해 헤드 노드에서 트래버스해야 하는 프로세스는 **링크된 목록의 순차적 액세스 특성**을 보여줍니다.
* ⏳ 직접 인덱스 액세스가 가능한 배열 목록과 달리 링크된 목록은 **특정 노드에 도달하기 위해 헤드에서 트래버스**해야 하므로 시간 지연이 발생합니다.
* 🛠 꼬리 포인터가 없으면 모든 추가 작업을 위해 **머리부터 시작**해야 하므로 요소를 추가할 때 시간이 비효율적일 수 있습니다.
* 🔍 **50과 같은 값을 검색하려면 값을 찾거나 목록의 끝에 도달할 때까지 각 노드를 순차적으로 확인**해야 하므로 링크된 목록의 선형 검색 특성이 강조됩니다.
* ✂ 노드를 제거하려면 먼저 트래버스를 통해 노드를 찾은 다음 링크를 조정하여 삭제된 노드를 우회해야 하는데, **노드를 찾으면 간단하게 처리**할 수 있습니다.
* 🔄 링크된 목록에 대한 논의에는 **단일 링크된 목록, 이중 링크된 목록, 순환 링크된 목록**과 같은 변형이 포함되며, 각각 고유한 탐색 및 조작 기능을 제공합니다.
* 📊 배열 목록과 링크된 목록을 비교할 때, **배열 목록은 인덱싱된 요소에 대해 일정한 시간 액세스**를 제공하는 반면 **링크된 목록은 데이터를 이동할 필요 없이 동적 크기 관리**가 뛰어납니다.

리스트(list)를 아시나요? array list와 linked list의 개념과 차이를 한방에 정리합니다! 2년 전 영상보다 더욱 업그레이드된 영상을 지금 만나보세요!!

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

리스트 ADT 개념 소개 및 활용 예시

리스트는 값들을 저장하는 추상 자료형으로 순서가 있으며 중복을 허용한다.

객관식 문제의 정답 저장에 활용 가능하다.

프로그래밍 언어 순위 저장에도 적합하다.

셋이나 맵보다 적절하지 않은 상황이 아니라면 대부분 리스트를 사용한다.

TV에서 여러 개의 데이터를 읽어올 때 임시 저장소로 사용 가능하다.

배열을 사용하여 리스트를 구현한다.

append 연산은 배열의 끝에 데이터를 추가한다.

insert 연산은 특정 인덱스에 데이터를 추가하며, 데이터 시프트가 발생한다.

get 연산은 특정 인덱스의 데이터를 가져온다.

배열이 가득 차면 더 큰 배열을 생성하고 기존 데이터를 복사한다.

contains 연산은 특정 값이 존재하는지 확인하며, 최악의 경우 모든 아이템을 확인해야 한다.

remove 연산은 특정 값을 제거하며, 데이터 시프트가 발생한다.

move 연산은 특정 인덱스의 값을 제거하며, 데이터 시프트가 발생한다.

노드를 연결하여 리스트를 구현하며, 각 노드는 값과 다음 노드를 가리키는 포인터를 갖는다.

어레이 리스트와 달리 메모리 공간에 연속적으로 저장되지 않는다.

append 연산은 새로운 노드를 생성하여 리스트의 끝에 추가한다.

insert 연산은 새로운 노드를 생성하여 특정 위치에 추가한다.

get 연산은 헤드 노드부터 시작하여 특정 위치의 노드를 찾아 값을 가져온다.

contains 연산은 헤드 노드부터 시작하여 특정 값을 찾는다.

remove 연산은 특정 값을 가진 노드를 찾아 제거한다.

removeAt 연산은 특정 인덱스의 노드를 제거한다.

싱글 링크드 리스트, 더블 링크드 리스트, 순환 링크드 리스트가 있다.

어레이 리스트와 링크드 리스트 비교 및 결론

어레이 리스트는 배열을, 링크드 리스트는 노드 연결을 사용한다.

데이터 접근 시간은 어레이 리스트가 상수 시간, 링크드 리스트는 위치에 따라 변한다.

삽입/삭제 시간은 둘 다 상수 시간이지만, 어레이 리스트는 데이터 시프트, 링크드 리스트는 위치 이동 시간이 발생할 수 있다.

리스트 크기 확장은 링크드 리스트가 유리하다.

CPU 캐시 활용은 어레이 리스트가 유리하다.

성능 면에서 큰 차이가 없으며, 상황에 맞게 선택하면 된다.

많은 경우 어레이 리스트 사용을 권장하는 경향이 있다.