링크드 리스트(Linked List)란?
링크드 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조를 말한다.
간단하게 말해 노드를 연결시킨 자료구조를 뜻한다.
링크드 리스트는 크기가 정해져 있는 배열과는 달리
리스트의 길이가 가변적이라는 큰 특징을 가지고 있다.
배열은 크기를 지정한 후 모자라게 되면 메모리를 더 할당하고
배열의 데이터를 복사해야 하는 번거로움과 비효율적인 측면이 있는데
링크드 리스트는 단순히 노드만 추가로 연결하면 되므로
리스트의 사이즈를 조정하는 데 상당한 유연함을 보인다.
그렇다고 무조건 링크드 리스트가 좋은 것만은 아니다.
왜냐하면 링크드 리스트는 데이터의 추가/삽입/삭제가 용이하다는 장점도 있지만
순차적으로 탐색하지 않으면 특정 위치의 요소에 접근하기가 어려워 탐색 속도가 떨어지는 단점이 있기 때문이다.
그렇기 때문에 데이터가 자주 추가되거나 가변적으로 운용해야 하는 프로그램에서는 링크드 리스트를 쓰는 것이 좋겠고
데이터의 변경이나 탐색이 주가 된다면 배열을 쓰는 것이 좋을 것이다.
다만 연결 리스트라고 해서 반드시 순차 탐색만 하지는 않는다.
B+Tree 자료구조를 사용하면 데이터의 추가/삭제/조회/정렬 모두 가능하다.
head와 tail
링크드 리스트의 맨 앞 노드는 head라 칭하고
마지막 노드는 tail이라고 칭한다.
보통 구현의 용이함을 위해 head와 tail의 데이터 필드는 사용하지 않는다.
노드를 추가하거나 삭제할 때 맨앞 노드인지 맨뒤 노드인지 확인할 필요 없이
중간 노드인가만 고려하면 되기 때문이다.
사용의 용이성을 위해 head와 tail은 더미노드로 두는 것이 좋다.
연결 리스트의 종류
1. 단순 연결 리스트
다음 노드에 대한 참조만을 가지고 있는 가장 단순한 형태이다.
마지막 요소를 찾으려면 리스트 끝까지 가야 하기 때문에 시간복잡도는 O(n)을 갖는다.
보통은 큐를 구현할 때 이 방법을 사용한다.
단순 연결 리스트는 head 노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점이 있다.
중간 어딘가에서도 마찬가지로 다음 노드에 대한 참조 주소를 잃어버리면
그 뒤쪽 자료를 모두 유실하게 되기 때문에 안정적인 자료구조는 아니다.
2. 이중 연결 리스트
다음 노드에 대한 참조뿐 아니라 이전 노드에 대한 참조도 쌍으로 가능하다.
뒤로 탐색하는 게 더 빠른 장점도 있고 현재 노드를 삭제하는 것이 단순 연결 리스트에 비해 훨씬 간단하다는 장점도 가지고 있다.
왜냐하면 단순 연결 리스트는 현재 가리키고 있는 노드를 삭제하려면
한 번에 지울 수가 없고 O(n)이 될 수밖에 없는데
이중 연결 리스트는 양방향 참조가 가능하기 때문에 상대적으로 간단하게 삭제가 가능하다.
다만 관리해야 할 참조가 2개나 있기 때문에 삽입하거나 정렬하는 경우
작업량이 더 많고 자료구조의 크기가 약간 더 커진다.
이중 연결 리스트는 head와 tail 노드 둘 중 하나를 가지고 전체 리스트를 다 순회할 수 있기 때문에 중간에 참조 주소를 잃어버려도 복구가 가능하다.
3. 원형 연결 리스트
단순 연결 리스트에서 마지막 요소가 null 대신 맨 처음 요소를 가리키게 하면
원형 연결 리스트가 된다.
이중 연결 리스트의 처음과 끝을 이어도 이중 원형 연결 리스트를 만들 수 있다.
원형 연결 리스트는 스트림 버퍼의 구현에 많이 사용되며
이미 할당된 메모리 공간을 삭제하고 재할당하는 부담이 없기 때문에
큐를 구현하는 데에도 적합하다.
4. 청크 리스트
배열 + 리스트의 장점을 합친 것이다.
리스트의 멤버가 배열이다.
CPU에 캐시 기능이 있는 경우 지역성이 떨어지는 연결 리스트는 심각한 성능저하를 불러오는데
이를 보완하기 위해 리스트의 메법를 레코드의 배열로 하는 것이다.
이 청크 리스트의 발전된 버전이 바로 B+Tree이다.
시간복잡도
배열과는 달리 첫 번째 데이터의 추가/삭제는 O(1)의 시간복잡도를 갖는다.
배열의 경우엔 데이터의 추가/삭제가 일어나면 그 뒤쪽 데이터를 모두 이동해야 하지만 연결 리스트는 그럴 필요가 없기 때문이다.
다만 처음이 아닌 중간에 데이터를 추가하거나 삭제할 때는
해당 데이터를 검색하는 데 시간이 걸리기 때문에 O(n)의 시간복잡도를 갖는다.
정렬의 경우엔 O(n log n)의 시간복잡도를 갖는데, 이를 보완한 것이 바로 B+Tree이다.
