배열(Array)은 순차적으로 연결된 공간에 데이터를 나열하는 구조인데 비해 연결리스트(Linked List)는 떨어진 곳에 존재하는 데이터를 포인터(Pointer)로 연결해서 관리한다. 따라서 연결리스트는 데이터와 다음 데이터의 주소를 가리키는 포인터를 하나의 저장 단위로 한다. 이 하나의 저장 단위를 노드(Node)라고 한다.
- 장점
- 배열처럼 데이터 공간을 미리 할당하지 않아도 됨
- 중간에 데이터를 추가/삭제시 연결을 위한 포인터 값만 바꾸면 되므로, 배열처럼 데이터를 옮겨줘야하는 작업이 불필요함 - 단점
- 데이터 뿐만 아니라 연결을 위한 데이터도 함께 관리해야 하므로 저장공간 효율이 좋지 않음
- 데이터가 메모리상에 순차적으로 저장된다는 보장이 없으므로 데이터 접근 속도가 느림
연결리스트의 종류로는 단방향 연결리스트(Singly Linked List), 양방향 연결리스트(Doubly Linked List), 원형 연결리스트(Circular Linked List) 등이 있다. 단방향 연결리스트는 다음 노드를 가리키는 포인터만 존재하는 반면, 양방향 연결리스트는 이전 노드를 가리키는 포인터도 존재한다. 그리고 원형 리스트는 마지막 노드가 빈 공간이 아닌 첫번째 노드를 가리켜 순환하는 구조로 되어있다. 여기서 더 확장하여 양방향 연결리스트와 원형 연결리스트를 합친 양방향 원형 연결리스트(Doubly Circular Linked List)도 존재한다.
< Singly Linked List 구현하기 >
< Doubly Linked List 구현하기 >
'자료구조 & 알고리즘' 카테고리의 다른 글
| [파이썬] 재귀 호출 (Recursive Call) (0) | 2021.03.21 |
|---|---|
| [파이썬] 버블 정렬, 삽입 정렬, 선택 정렬 구현하기 (0) | 2021.03.20 |
| [파이썬] 힙(Heap) 직접 구현하기 (0) | 2021.03.17 |
| [파이썬] 이진 탐색 트리(Binary Search Tree) 직접 구현하기 (0) | 2021.03.17 |
| [파이썬] Hash Table 구현과 Hash Collision 해결 기법 (0) | 2021.03.16 |