1. 연결리스트 (Linked List, 링크드리스트)
각 노드(데이터의 묶음)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조. 노드의 포인터가 이전/다음 노드와의 연결을 담당.
- 맨 앞의 노드 -> 헤드(Head)
- 맨 뒤의 노드 -> 테일(tail)
- 아무 데이터가 없는 노드 -> 더미노드
- 다음 데이터를 가리키는 주소값 -> 포인터(Pointer)
2. 장점과 단점
📌 장점
- 연결된 노드의 중간에 자료의 추가/삭제가 편리함 -> 시간복잡도 O(1)
- 추가/삭제를 자주하면 연결리스트를 사용하는게 유리.
- 리스트의 길이가 가변적임 (크기가 정해진 배열은 비효율적임)
📌 단점
- 특정 위치의 데이터 검색시 시간복잡도 O(n)
- 탐색/정렬을 자주하면 배열을 사용하는게 낫다.
- 연결 관계만 존재해서 특정 노드를 불러내기 어려움
- 중간데이터 삭제시, 앞뒤 데이터를 연결하는 코드가 추가로 필요
- 다음 데이터 연결을 위해 별도의 주소공간 필요 -> 저장공간 효율이 낮다
3. 연결리스트의 종류
(1) 단일 연결리스트 (Singly Linked List)
- 다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트.
- 각 노드에 자료 공간과 한 개의 포인터 공간
- Head노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점
- 다음 노드를 참조하는 주소 중 하나가 잘못되면 뒤쪽 자료가 유실되는 단점
(2)이중 연결 리스트 (Doubly Linked List)
- 두 개의 포인터 공간을 가짐, 각각 앞 노드와 뒤의 노드를 가리킴
- 뒤로 탐색시 빠르다는 장점
단일 연결 리스트는 현재의 노드를 삭제하는 것이 앞뒤 노드를 연결 시켜줘야 하므로 복잡(O(n))하지만 이중 연결 리스트는 더 간단하다는 장점.단일 연결 리스트보다 손상에 강함 ->Head와Tail노드를 가지고 전체 리스트를 순회해서 끊어진 체인을 복구하는 게 가능하다.- 단점은 참조가 두 개이기 때문에 작업량이 더 많으며 자료구조의 크기가 더 커짐.
- 보정 알고리즘을 구현하지 않으면 노드를 잃어버릴 수 있음.
(3) 원형 연결 리스트 (Circular linked list)
- 단순 연결 리스트에서 마지막 원소가 Null(None) 대신 처음 원소를 가리킴.
- 이중 연결 리스트의 처음과 끝을 이으면 이중 원형 연결 리스트.
- 메모리 재할당의 부담이 적어서 큐(queue)를 구현하는 데에 적합.(스트림 버퍼 구현에도 많이 사용)
- 연결 리스트의 시작점에 더미노드를 추가해 처음과 마지막을 구분.(전체 크기 카운트시 더미노드는 제외)
참고 자료(References)
https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8
https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8
Python 서버 개발자