[자료구조] 연결리스트
연결리스트를 알아보기 전에 먼저 [자료구조 Array]의 시간복잡도를 간단히 알아보자.
1. 접근
찾고자 하는 값이 몇 번째 인덱스인지 알고 있다면 O(1)의 속도로 찾을 수 있다.
2. 검색
인덱스를 알지 못할 때 원하는 값을 찾기 위해서는 배열을 모두 탐색해야 한다. 따라서 시간복잡도는 O(n)이 된다.
3. 추가
데이터들이 순차적으로 저장되어 있기 때문에 맨 처음이나 그 이후 데이터가 추가될 경우 데이터들을 전부 한 칸씩 뒤로 미뤄야 한다. 이때 시간복잡도는 O(n)이 되고, 만약 배열에 공간이 남아있을 때 데이터를 맨 뒤에 추가한다면 이 때는 O(1)이 된다.
4. 삭제
데이터 추가와 경우가 같다. 삭제하려는 데이터의 위치가 맨 뒤가 아니라면 O(n)의 시간복잡도를 갖는다.
삭제하려는 데이터의 위치가 만약 맨 뒤이고 배열에 공간이 남아있다면 O(1)의 시간복잡도를 갖는다.
연결리스트 LinkedList
어떤 데이터들을 담는 Array에서 삽입과 삭제가 빈번하게 일어난다면 매우 비효율적일 것이다.
이와 같은 문제를 해결하기 위해 연결리스트라는 자료구조가 등장했다. 탐색은 O(N)으로 느리지만 삽입과 삭제 연산은 O(1)로 매우 빠르기 때문에 삽입과 삭제가 잦은 상황에서 사용된다.
각 노드들은 데이터를 가지고 있는 영역과 다음 노드를 가리킬 수 있는 영역으로 나뉜다.
이렇게 연결된 자료구조에서 맨 앞 부분을 Head, 맨 뒷부분을 Tail이라고 한다.
- Head: 가장 앞에 위치한 노드
- Tail: 가장 뒤에 위치한 노드
이 때 탐색은 Head부터 Tail까지 일일이 확인해야 하므로 O(n)이라는 시간이 소요된다.
삽입이나 삭제의 경우, 인접한 곳의 선을 끊고 다시 연결만 해주면 되기 때문에 O(1)이라는 시간이 소요된다.
이중 연결 리스트
위 형태를 가지는 연결리스트는 한 방향으로만 이어져 있는 단일 연결리스트이다.
그렇기 때문에 역방향으로 탐색할 수 없는 단점이 있다.
이를 해결하기 위해 이전 노드를 가리킬 수 있는 영역까지 확장하여 특정 노드의 앞, 뒤 노드를 이어줄 수가 있게 된다.
위 내용을 요약하여, 연결리스트의 가장 큰 특징들을 알아보자
- 연결리스트는 동적으로 크기를 변경할 수 있다.
- 특정 위치에 노드를 삽입, 삭제할 때 인접 노드들의 이동이 필요하지 않다. 단순히 연결을 끊어주거나 이어주거나 하면 되기 때문에 시간이 O(1)로 굉장히 빠르다.
- 특정 노드에 접근하기 위해서는 전체 노드들을 순회해야 한다. 최악의 경우 O(n)의 시간이 소요된다.