[DS] LinkedList

❗LinkedList란?

LinkedList란 각 데이터 요소가 노드 형태로 존재하고 각 노드가 다음 노드를 가리키며 연결된 형태를 가진다. 연결 구조 덕분에 데이터의 삽입과 삭제가 유연하게 가능하여 이 점에서는 배열보다 유리하다고 할 수 있다.

노드(Node)	연결 리스트에서 각 데이터를 담고 있는 단위 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있음
헤드(Head)	리스트의 첫 번째 노드를 가리키는 포인터 연결 리스트는 첫 번째 노드부터 시작해서 다음 노드를 따라가면서 데이터를 조회
포인터(Pointer)	다음 노드의 위치를 가리키는 참조 연결 리스트는 각 노드가 포인터를 통해 다음 노드의 위치를 알고 있음

 

 

 

❗ LinkedList 종류

• 단일 연결 리스트(Singly Linked List):
  • 각 노드가 하나의 포인터(next)만을 가지고 이 포인터는 다음 노드를 가리킨다.
  • 마지막 노드의 포인터는 null 또는 None으로 설정되어 리스트의 끝을 나타낸다.
  • 단방향으로만 순회할 수 있다.
• 이중 연결 리스트(Doubly Linked List):
  • 각 노드가 두 개의 포인터(prev, next)를 가지며 prev는 이전 노드를, next는 다음 노드를 가리킨다.
  • 리스트를 양방향으로 순회할 수 있다.
  • 이중 연결 리스트는 단일 연결 리스트에 비해 더 많은 메모리를 사용하지만 노드의 삽입과 삭제가 더 효율적이다.
• 원형 연결 리스트(Circular Linked List):
  • 마지막 노드의 next 포인터가 null이 아닌 첫 번째 노드를 가리키는 형태이다.
  • 리스트의 처음과 끝이 연결된 구조로 무한 순환이 가능해 리스트의 순회를 반복적으로 할 때 유용하다.
  • 단일 또는 이중 연결 리스트와 같이 단방향 또는 양방향으로 구현할 수 있다.

 

 

 

❗ LinkedList 활용 예시

• 메모리 효율적인 데이터 저장: 메모리 크기가 제한된 환경에서 유동적인 크기의 데이터를 저장할 때 유용
• Undo 기능 구현: 텍스트 에디터의 Undo 기능 등에서 각 상태를 연결 리스트의 형태로 저장하여 이전 상태로 쉽게 돌아갈 수 있음
• 데이터 캐싱: 이중 연결 리스트와 해시 테이블을 결합하여 LRU(Least Recently Used) 캐싱 메커니즘을 구현할 수 있음

 

 

❗LinkedList 구현

https://radiant515.tistory.com/732

[Python] LinkList 구현하기