자료구조 (Double LinkedList)

Double LinkedList

• 이중연결리스트는 단일연결리스트의 제한된 흐름을 개선하려 만든 자료구조이다.
• 단일연결리스트는 다음 노드의 위치를 가리키는 next만 가졌다면, 이중연결리스트는 이전의 노드를 가리키는 prev도 지원한다.
• 참조값을 이용하여 포인터를 좌,우측으로 노드에 접근할 수 있다.

Double LinkedList 구성

• Head : 단일연결리스트에서와 같은 역할을 한다.
  (첫 번째 노드를 가리키는 변수)
• Tail : 마지막 노드를 가리키는 노드, tail을 이용하여 마지막 노드에 빠르게 접근 할 수 있다.
• Node : 데이터와 next, prev 노드로 접근할 수 있는 참조 값을 가지고 있다.

Doubli LinkedList 장점과 단접

• 장점
  • 단일연결리스트와 동일하게 데이터의 크기가 예측불가 시 사용
  • 배열보다 메모리 절약
  • Head와 Tail을 이용하여 양방향으로 빠르게 접근 가능
• 단점
  • 단일연결리스트보다 복잡
  • 노드의 참조값을 next, prev 방향으로 저장하여 단일연결리스트보다 메모리를 더 많이 사용

Double LinkedList 삽입

1. 최초 노드 삽입 (next, prev 기준은 새로만든 노드)
   • head와 tail은 null값을 저장
   • pointer가 head를 가리키고 있을 때 새로운 노드 생성
   • 새로운 노드의 next 노드 참조값을 head에, prev 노드 참조값을 tail에 저장
2. 맨 앞 노드 삽입 (next, prev 기준은 새로만든 노드)
   • pointer가 head를 가리키고 있을 때 새로운 노드 생성
   • next 노드의 참조값을 새로운 노드의 right변수에 저장
   • 새로운 노드의 참조값을 perv 노드의 left변수에 저장
   • 새로운 노드의 참조값을 head에 저장
3. 맨 뒤 노드 삽입 (next, prev 기준은 새로만든 노드)
   • pointer가 tail을 가리키고 있을 때 새로운 노드 생성
   • prev 노드의 참조값을 새로 만든 노드 left 변수에 저장
   • 새로 만든 노드의 참조값을 prev 노드의 right 변수에 저장
   • 새로 만든 노드의 참조값을 tail에 저장
4. 중간 노드 삽입 (next, prev 기준은 새로만든 노드)
   • pointer가 next 노드를 가리키고 있을 때 새로운 노드 생성
   • prev 노드의 참조값을 새로만든노드의 left 변수에 저장,
     새로 만든 노드의 참조값을 prev 노드의 right 변수에 저장
   • next 노드의 참조값을 새로 만든 노드의 right 변수에 저장,
     새로 만든 노드의 참조값을 next 노드의 left 변수에 저장

Double LinkedList 삭제

1. 맨 앞의 노드 삭제
   • 삭제할 노드에 pointer가 위치
   • next 노드의 left 변수에 null 값 저장
   • 삭제할 노드의 right 변수에 null 값 저장
   • head가 삭제할 노드의 참조값을 참조 -> next 노드의 참조값의 right변수로 참조값 변경
2. 맨 뒤의 노드 삭제
   • 삭제할 노드에 pointer가 위치
   • 삭제노드 prev 노드의 right변수에 null값을 저장
   • 삭제할 노드의 left 변수에 null값 저장
   • Tail이 삭제할 노드의 참조값을 참조 -> prev 노드의 참조값을 left 변수로 참조값을 변경
3. 중간 노드 삭제
   • 삭제할 노드에 pointer가 위치
   • prev 노드의 right 변수에 next 노드의 left 변수 저장
   • next 노드의 left 변수에 prev 노드의 right 변수 저장
   • 삭제할 노드의 left, right 변수에 null값 저장
4. 노드가 하나만 있을 때 삭제
   • 삭제할 노드에 pointer 위치
   • head, tail에 null 값 저장