연결리스트 (Linked List)
- 각 요소를 포인터로 연결하여 관리한다.
- 선형 자료구조이다.
- 각 요소를 노드라고 칭하며, 데이터 영역과 포인터 영역으로 구성된다.
- 요소를 제한 없이 추가 할 수 있다.
- 탐색(Search)에 O(n)이 소요된다.
- 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
- 단일 연결 리스트(Singly Linked List), 이중 Doubly Linked List, 선형 Circular Linked List
요소 삭제
-
일반 배열
→ O(n) 선형시간이 소요된다. 빠지고 나서 빈 공간을 한칸 씩 당겨서 매꿔야하기 때문이다.
-
연결 리스트
→ O(1) 삭제 후, 포인터를 그 다음 것으로 옮긴다.
메모리차이
-
일반 배열
⇒ 메모리를 순차적으로 차지한다.
-
연결 리스트
⇒ 퍼져있어서 참조하고 있는 메모리를 포인터를 통해 찾는다.
연결리스트 이미지 예시

Linked List Data Structure - GeeksforGeeks