연결 리스트

원소를 저장할 때 다음 원소가 어디 있는지를 함께 저장하는 자료구조. 배열과 달리 원소들이 메모리 여기저기 흩어져 있어도 되고, 대신 몇 번째 원소인지를 바로 찾을 방법이 없다. 배열과 연결 리스트 모두 원소 사이에 순서가 있어서 선형 자료구조로 묶인다. 트리, 그래프, 해시는 비선형이다.

링크를 바꾸는 순서

노드를 끼울 때는 새 노드가 뒤를 먼저 가리키게 하고, 그 다음에 앞 노드가 새 노드를 가리키게 해야 한다. 순서를 뒤집으면 기존 링크가 끊기면서 뒤쪽 전체를 잃는다.

function SLL.insert_after_head(num)
  set new_node = node(num)
  new_node.next = SLL.head.next    // 새 노드가 뒤를 먼저 가리킨다
  SLL.head.next = new_node         // 그 다음에 앞을 바꾼다

삭제는 반대로 지울 노드의 앞 노드가 그 다음을 가리키게 바꾼다. 노드를 실제로 지우는 게 아니라 아무도 가리키지 않게 만드는 것이다.

Iterator로 위치를 쥐고 쓰기

Iterator는 리스트 안의 위치를 가리킨다. k번째 자리를 찾아가는 건 여전히 O(N)이지만, 한 번 잡아두면 그 근처에서의 삽입, 삭제, 읽기가 전부 O(1)이다. 연결 리스트의 성능을 실제로 뽑아 쓰려면 이렇게 써야 한다. 다만 remove() 앞에는 반드시 next()가 와야 한다. 방금 지나온 원소를 지우는 메서드이기 때문이다.

길이, 교차점, 사이클 찾기

면접에서 자주 나오는 문제가 셋 있다. 원형 리스트의 길이는 시작 노드를 기억해두고 같은 노드가 다시 나올 때까지 돌면 시간 O(N), 공간 O(1)에 구한다. 두 리스트가 만나는 지점은 각각 끝까지 가서 길이를 재고, 긴 쪽을 길이 차이만큼 먼저 보낸 뒤 둘을 동시에 한 칸씩 전진시키면 만나는 곳이 답이다. 시간 O(A+B), 공간 O(1)이다. 사이클이 있는지는 한 칸씩 가는 커서와 두 칸씩 가는 커서를 같은 곳에서 출발시켜 판단한다. 사이클이 있으면 반드시 만나고, 없으면 빠른 쪽이 먼저 끝에 도달한다. 플로이드 순환 찾기 알고리즘이라고 한다.

단일, 이중, 원형

단일 연결 리스트는 다음만 가리킨다. 앞뒤 끝을 head와 tail로 들고 있어야 하는데, head가 없으면 어디서 시작할지 모르고 tail이 있으면 끝인지 판단하는 데 추가 처리가 필요 없기 때문이다. 한 번 지나가면 되돌아올 수 없다.

이중 연결 리스트는 앞뒤를 모두 가리킨다. 되돌아갈 수 있는 대신 삽입과 삭제 때 고칠 링크가 두 배다.

원형 연결 리스트는 양 끝을 이어 붙인 것이다. head.prev가 곧 tail이라 tail을 따로 들 필요가 없고, 계속 따라가면 시작점으로 돌아온다.

배열과의 비용 차이

텍스트 에디터의 커서가 교과서적인 예다. 커서를 옮기고, 그 자리에서 글자를 넣거나 지우는 일을 계속 반복한다. 커서가 이미 그 위치를 가리키고 있으니 삽입과 삭제가 O(1)이다. 배열이었다면 글자 하나 넣을 때마다 뒤를 전부 밀어야 한다.

N이 크고, 돌아다니다가 그 자리에서 넣고 빼는 상황에 떠올리면 된다.

위치를 모르면 사라지는 이점

삽입과 삭제가 O(1)인 것은 그 위치를 이미 알고 있을 때뿐이다. k번째에 넣으라고 하면 k번 걸어가야 하니 O(N)이다. 이 구조의 장점을 살리려면 위치를 손에 쥔 채로 작업해야 한다.

관련

• 배열
• 스택
• 해시 충돌

출처

• 바킹독 실전 알고리즘 0x04강 - 연결 리스트
• 코드트리 자료구조 - LinkedList