연결리스트 (Linked List)

• 각 요소를 포인터로 연결하여 관리한다.
• 선형 자료구조이다.
• 각 요소를 노드라고 칭하며, 데이터 영역과 포인터 영역으로 구성된다.
• 요소를 제한 없이 추가 할 수 있다.
• 탐색(Search)에 O(n)이 소요된다.
• 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
• 단일 연결 리스트(Singly Linked List), 이중 Doubly Linked List, 선형 Circular Linked List

요소 삭제

1. 일반 배열

   → O(n) 선형시간이 소요된다. 빠지고 나서 빈 공간을 한칸 씩 당겨서 매꿔야하기 때문이다.

2. 연결 리스트

   → O(1) 삭제 후, 포인터를 그 다음 것으로 옮긴다.

메모리차이

1. 일반 배열

   ⇒ 메모리를 순차적으로 차지한다.

2. 연결 리스트

   ⇒ 퍼져있어서 참조하고 있는 메모리를 포인터를 통해 찾는다.

연결리스트 이미지 예시

Linked List Data Structure - GeeksforGeeks