연결 리스트 Linked List

Linked list는 순차적 자료구조의 마지막이다.

한 방향과 양 방향이 있다.

• 배열 vs 연결 리스트

배열은 연속된 공간에 메모리를 차지하고, 인덱스를 통해 값을 수정 및 첨가할 수 있다.
이에 반해 연결 리스트는 그것이 아니다. 배열과 대조적으로 연속되어 있지 않고 흩어져있다.
대신 메모리 주소를 따라갈 수 있다. 3->9->->-1->2->None(Null)
여기서 실제 데이터 값을 key라고 하며, 그 다음 주소를 link라고 부른다. 이렇게 (key, link) 이 쌍을 하나의 node라고 부른다. 이 노드들이 연결되어 있는 것이다.

맨 앞의 노드를 head node라고 하는데, index 2에 있는 값은? 이라고 물어보면 상수 시간 내에 바로 찾을 수 없다. 왜냐하면 배열과 달리 링크를 따라가야 하기에, head node부터 차례로 주소를 따라가서 "index 2에 있는 것은 값이 -1이다." 라고 말해야 하기 때문이다. 즉 100번째 값을 알고 싶다면, 100번을 따라가야 하는 것이기에 길이만큼의 시간이 든다.

Q. 그렇다면 Linked List를 왜 사용할까?
예를 들어 배열 A = [3, 9, -1, 2] 가 있다고 할 때, index2자리에 5를 insert하고 싶다고 가정하자. 이 때 -1과 2는 오른쪽으로 한 칸 씩 이동해야 하고, 이 빈 자리에 insert를 한다. 만약 뒤에 있는 값들이 굉장히 많다면?! 모두 옮겨줘야 하기에 꽤 불편할 것이다. (상수 시간이 안 될 수도 있다.)

하지만 이에 반해 linked list를 고려해본다면, 단순히 5라는 노드 하나를 추가하고 9가 가리키는 주소를 -1이 아니라 5로 바꾸고 5에서 -1로 주소를 가리키면 끝난다. 나머지 노드들을 건드릴 필요가 없게 되는 것이다!
insert하는 것이 상수시간이 된다.

그렇다면 본격적으로 linked list에 대해 알아보자.

• 1. 한 방향 연결 리스트
     말 그대로 한 방향으로만 주소를 가리키는 것이다. 3 9 -1 2면 오른쪽으로 한 방향으로만 가리키고 반대로 가리키지는 않는다. 즉 키와 링크가 하나다.
• 2. 양 방향 연결 리스트
     위와 달리 양 방향으로 주소를 가리키는 링크를 각 노드가 가지고 있다. 여기서는 키는 하나지만 링크는 두 개이다.