연결 리스트(Linked List)란?
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조이다.
포인터는 프로그래밍 언어에서 다른 변수, 혹은 그 변수의 메모리 공간 주소를 가리키는 변수를 말한다.
이해하기 쉽게 말하자면, 다음 노드의 주소값을 가지며, 그 다음 노드와 연결을 담당해주는 역할이라고 생각하면 된다.
특징
- 각 노드는 동적으로 할당되므로, 노드들 사이의 주소 값은 연속적이지 않음
- 배열과 달리 중간 값을 인덱싱하여 바로 접근하는 것이 불가능
- 연결 리스트 탐색은 보통 헤드로부터 시작하여 각 노드가 가리키는 다음 노드로 이동함
종류
단일 연결 리스트(Singly Linked List)
단일 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 가지며, 마지막 노드는 null을 가리킨다. 그러나 만약 어떤 노드의 포인터가 잘못된 주소를 가리키게 되면, 그 이후의 노드들과 연결이 끊어져 체인이 끊어진 것처럼 되어 안정적인 자료구조로 보기 어렵다.
이중 연결 리스트(Doubly Linked List)
이중 연결 리스트는 각 노드가 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 가지며, 양방향 탐색이 가능하다.
이중 연결 리스트의 장단점
- 원하는 데이터가 앞쪽에 가까우면 head부터, 뒤쪽에 가까우면 tail부터 탐색하여 빠르게 찾을 수 있다.
- 이중 연결 리스트는, 순차적으로 모든 노드를 탐색해야 하는 단일 연결 리스트의 단점을 보완한다.
- 다음 참조 주소가 끊어져도 이전 노드의 주소가 남아 있어 중간 노드 삭제 및 추가가 용이하다.
- 각 노드가 두 개의 포인터를 가지므로 자료구조의 크기가 단일 연결 리스트보다 크다.
- 삽입이나 정렬 시, 두 개의 참조를 모두 갱신해야 하므로 작업이 더 많아진다.
head: 연결 리스트의 첫 번째 노드를 가리키는 포인터
tail: 연결 리스트의 마지막 노드를 가리키는 포인터
원형 연결 리스트(Circular Linked List)
단일 또는 이중 연결 리스트에서 마지막 노드(tail)가 첫 번째 노드(head)를 가리키는 구조이다.
장단점(배열 vs 연결 리스트)
연결 리스트와 배열은 서로의 장단점을 보완해주고 있기 때문에, 보통 연결 리스트를 설명할 때 배열과 묶어서 설명한다.
연결 리스트의 장점
동적 메모리 할당: 연결 리스트는 실행 중에도 데이터 크기를 유연하게 조정할 수 있어, 미리 데이터 크기를 알 필요가 없다.
삽입/삭제 용이: 중간에 있는 요소를 삽입하거나 삭제할 때, 연결 리스트는 포인터만 조정하면 되므로 상대적으로 간편하다.
메모리 효율: 연결 리스트는 불필요한 메모리를 미리 할당하지 않아 메모리 사용 효율성이 높다.
데이터 타입의 다양성: 연결 리스트는 다양한 타입의 데이터를 한 리스트 안에서 저장할 수 있어, 유연성이 높다.
연결 리스트의 단점
메모리 사용 비효율: 각 노드는 데이터와 함께 다음 노드를 가리키는 포인터도 저장해야 해서 추가적인 메모리를 필요로 하다.
코드 복잡성: 연결 리스트를 사용하면 삽입과 삭제를 위해 추가적인 코드가 필요하므로 배열에 비해 코드가 복잡해질 수 있다.
시간 복잡도: 특정 요소를 찾는데 있어서는 배열에 비해 시간이 더 걸릴 수 있다.
시간 복잡도
접근(Access): O(n)
- 인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 가면 됨.
- 마지막 노드에 접근하려면 head에서 다음 노드로 n-1번 가야함.
- 최악의 경우 시간 복잡도: O(n)
탐색(Find): O(n)
- 가장 앞 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 갖는 데이터를 찾음.(선형 탐색)
- 연결 리스트 안에 찾는 데이터가 없거나 찾으려는 데이터가 마지막 노드에 있는 경우 n개의 노드를 모두 확인해야 함.
- 최악의 경우 시간 복잡도: O(n)
삽입/삭제(Insert/Delete): O(n)
- 리스트 시작에서 삽입, 리스트의 끝에 삽입(tail 포인터를 사용할 경우)
- 삽입, 삭제할 노드의 주변 노드들의 Link만 수정하면 됨.
- 삽입, 삭제가 실행되는 시간은 특정 값에 비례하지 않고 항상 일정함.
- 시간 복잡도: O(1)
- 특정 위치에 삽입 또는 삭제
- 특정 값을 찾기 위해 리스트를 순회하고, 찾은 노드 삭제
- 시간 복잡도: O(n)
삽입 또는 삭제: 배열은 데이터 이동이 필요, 연결리스트는 포인터만 변경
검색 또는 랜덤 액세스: 배열은 인덱스 활용, 연결리스트는 전체 순회
따라서, 삽입과 삭제가 중요한 경우에는 연결 리스트를, 검색이나 랜덤 액세스가 중요한 경우에는 배열을 사용하는 것이 좋다.
[참고 자료]
https://velog.io/@alsrl2313/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%9E%80-Linked-List
https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List?category=1010128
https://hyeinisfree.tistory.com/64
https://velog.io/@dayon_log/%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8-Linked-List
