<aside> 💡 연결리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조를 말한다. 데이터를 담고 있는 노드들은 포인터로 연결되어 있는데 노드의 포인터가 다음(next) 혹은 이전(prev) 노드와의 연결을 담당한다.

</aside>

분류

단일 연결 리스트(일방향)

• 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중 연결 리스트(양방향)

• 이중 연결 리스트는 단일 연결 리스트와 비슷하지만 포인터 공간이 두 개 있고 각 포인터는 이전 노드, 다음 노드를 가리킨다.

연산

• 삽입: O(1)
  • 배열의 경우, 중간에 삽입하려면 뒤에 있는 원소를 한 칸씩 밀거나 만약 배열이 꽉 찼다면 새 배열에 담아야 하는 등 O(n)의 시간이 소요된다.
  • 하지만 연결 리스트는 전후에 위치한 포인터 연결을 끊고 해당 노드에 연결만 시켜주면 되므로 O(1)의 시간복잡도로 삽입이 가능하다.
• 삭제: O(1)
  • 삭제도 마찬가지로 O(1).
• 탐색: O(n)

특징

• 배열과 달리 크기 늘리기가 매우 용이함 → & 메모리 낭비가 배열에 비해 덜 하다. 배열은 선언 시점에 사이즈 역시 선언해야 하기 때문.
• 배열은 인접한 주소공간을 차지하는 반면, 연결리스트 내 원소는 여기 저기 흩어져있고 포인터로 연결되어 있음 ⇒ 메모리 효율이 좋음.

구현

삽입