Double linked list

  • Single linked list에서는 추가된 노드가 항상 뒤쪽으로만 추가됨. prev만 가지고 있음
  • Double linked list는 Head와 Tail 두개의 Node를 미리 가지고 있음. 각 노드는 prev와 next도 가지고 있음

  • 초기화로, head의 next는 tail을, tail의 prev는 head를 가리키고 있음. tail->prev가 싱글링크드리스트의 pList역할을 하고 있음
  • 노드를 추가 하는 경우, 기존 싱글링크드리스트의 prev처리와 함께 새로 next처리도 해주면 됨. 그림 그려보며 이해하기

  • 이제 검색할때 head에서 tail까지 혹은 tail에서 head까지 검색 할 수 있음

  • 삭제 하는 법은 노드의 연결만 변경하면 됨

  • Single linked list에서도 dummy node인 Tail노드를 미리 만들어 두고 사용하면 노드 삭제가 좀더 쉬움

 

It's only fair to share...Share on Facebook
Facebook
Share on Tumblr
Tumblr
Share on Google+
Google+
Tweet about this on Twitter
Twitter
Email this to someone
email
Musicals, Travel, Photo, Coding, English, Cat