<TIL 20.06.14> Linked LIst

Linked List

• 자료구조를 구성하는 요소를 노드라 한다.
• 이름 그대로 노드와 노드 간의 연결(link)을 이용해서 리스트를 구현한 것이다.
• 첫 번째 노드를 'Head' 마지막 노드를'Tail'이라 한다.
• 전체 구조를 재할당하거나 재구성하지 않고, 목록의 특정 지점에 요소를 추가하거나 요소를 제거할 때 유리하지만 각 노드가 인덱스를 갖지 않는다.

1. Singly linked list ( 단일 연결 리스트 )

 

• 기존 배열에 비해 링크 데이터 항목들을 메모리나 디스크에 연속적으로 할당할 필요가 없다.
• 단일 연결 리스트는 이전 리스트의 값을 확인하기 위해서는 전체 목록을 처음부터 다시 순서대로 탐색해야 한다.

2. Doubly linked list ( 이중 연결 리스트)

 

• 이전 노드의 링크를 통해 O(1)의 시간 복잡도로 이전 노드를 찾을 수 있다.
• 이중 연결 리스트에서 노드를 추가하거나 제거하려면 단일 연결 리스트보다 많은 작업을 수행해야 한다.

시간 복잡도

• 삽입 : O(1)
• 삭제 : O(1)
• 탐색 : O(n)

실제 사용 사례

1. 이름 목록
2. 재고 품목 목록
3. 날짜 목록

 

 

 

이미지 출처 : Linked list - Wikipedia