-
[자료구조]링크드 리스트(Linked List)programming/Python 2021. 6. 8. 14:45
링크드 리스트 (Linked List)
링크드 리스트(Linked List), 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됩니다.
특징
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조입니다.
- 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조입니다.
- 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원합니다.
- 장점
- 배열은 미리 데이터의 공간을 할당해야하지만 링크드 리스트는 미리 데이터 공간을 미리 할당하지 않아도 됩니다.
- 단점
- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 낮습니다.
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느립니다.
- 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요합니다.
- 링크드 리스트 기본 구조와 용어
- 노드(Node): 데이터 저장 단위 (데이터 값, 포인터)로 구성되어 있습니다.
- 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간입니다.
다양한 링크드 리스트 구조
더블 링크드 리스트(Doubly linked list)
- 이중 연결 리스트라고도 부릅니다.
- 장점
- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능합니다.
원형 링크드 리스트(Circular linked list)
- 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트입니다.
- 장점
- 반복적인 순회에서 연결리스트의 끝을 체크해야 할 필요가 없습니다. 또한 HEAD와 같은 메타데이터가 필요하지 않기 때문에 시간, 메모리의 효율이 높습니다.
'programming > Python' 카테고리의 다른 글
[Python]Splitfloders 한줄로 Train/Test/Validation 나누기 (0) 2021.11.15 [Python]Python의 유용한 라이브러리들 (0) 2021.09.16 [자료구조]배열(Array), 큐(Queue), 스택(Stack) (2) 2021.05.20 [자료구조]Hash, Hashing, Hash Table (4) 2021.05.05 [OpenCV]_4. OpenCV 이미지 Processing (0) 2021.02.07