[자료구조] Linked List에 대해서 알아보자.
오늘은 Linked List(링크드 리스트)에 대해서 알아보는 시간을 갖도록 하겠다.
(1) 정의
- Linked List는 연결 리스트라고도 한다.
- 노드(Node)와 포인터(Pointer)를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는데 반해 linked list는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.
*노드(Node) : 데이터의 저장 단위 (데이터값, 포인터)로 구성
*포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
(2) 장점
- 미리 데이터 공간을 할당하지 않아도 된다. (배열은 미리 데이터 공간을 할당해야 함)
(3) 단점
- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않다.
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
- 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.
(3) 시간 복잡도
- 데이터 검색 : O(n)
- 첫 번째 데이터 추가/삭제 : O(1)
- 중간 데이터 추가/삭제 : O(1)
(4) 이중 연결 리스트 (Doubly linked list)
- 다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키게 하면 이중 연결 리스트가 된다.
- 뒤로 탐색하는게 빠르다.
- Head와 Tail노드를 갖고 있다면 둘 중 하나를 가지고 전체 리스트를 순회할 수 있기 때문에 끊어진 체인을 복구하는 게 가능하다. 때문에 단순 연결 리스트보다는 손상에 강한 편이다.
(5) 원형 연결 리스트 (Circular linked list)
- 단순 연결 리스트에서 마지막 원소가 null 대신 처음 원소를 가리키게 하면 원형 연결 리스트가 된다. 이와 비슷하게, 이중 연결 리스트의 처음과 끝을 서로 이으면 이중 원형 리스트를 만들 수 있다.
- 스트림 버퍼의 구현에 많이 사용한다.
- 이미 할당된 메모리 공간을 삭제하고 재할당하는 부담이 없기 때문에 큐를 구현하는 데에도 적합하다.
References
연결 리스트 - 위키백과, 우리 모두의 백과사전
ko.wikipedia.org