Linked list(연결 리스트)

연결 리스트란

각 노드가 다음 노드에 연결되어있는 선형 자료구조이다.

추상적 자료형인 리스트를 구현한 자료구조로, 연결 리스트란 말 그대로 어떤 데이터 덩어리를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다.

연결 리스트의 장점

배열 대비 연결 리스트가 가진 장점은 아래와 같다.

1. 배열은 배열이 길이 만큼 꽉 찬 상태에서 요소를 추가하면 배열의 길이의 두배에 해당하는 메모리를 미리 할당하여 그 만큼 불필요한 메모리를 사용하게 된다. (연결 리스트는 크기를 키우는데에 메모리 낭비가 적다.)
2. 배열은 push와 pop을 제외한 모든 배열의 요소 추가 및 제거 메서드에서 O(n)의 시간 복잡도를 가진다. 만약 첫 번째 인덱스에 요소를 추가해야 할 경우 나머지 모든 요소들을 오른쪽으로 한 칸씩 옮겨야한다. (연결 리스트는 첫 번째 인덱스에 요소 추가 시 0(1))

연결 리스트의 단점

배열 대비 연결 리스트가 가진 단점은 아래와 같다.

1. 일반 배열보다 많은 메모리를 차지한다.
2. 특정 index에 직접적인 접근이 불가능하다. 즉, 일반 배열은 index 번호를 통해 특정 위치의 값을 탐색하는 것이 시간복잡도 O(1)을 갖지만, 연결 리스트는 첫 노드부터 탐색해야 되기 때문에 시간복잡도가 O(n)이 된다.

This line appears after every note.