03-01 더블 링크드 리스트(Doubly Linked List)

*.링크드 리스트(Linked List)의 단점

-다음 노드를 가리키려는 포인터 때문에 각 노드마다 추가적인 메모리가 필요하다

-특정 위치에 있는 노드에 접근하기 위한 비용이 크고 시간이 많이 걸린다.

 

 

1.더블 링크드 리스트(Doubly Linked List)

1)정의 :링크드 리스트의 단점을 개선한 자료구조.

 -링크드 리스트에서 앞에 해당 노드를 가리크는 포인터를 추가적으로 갖고 있는 구조.

 

 

2.더블 링크드의 연산 및 함수원형 선언

-기존의 링크드 리스트와 차이가 없다.

3.더블 링크드 리스트 연산 구현

1)노드 생성 및 삭제 연산

2)노드 추가 연산

-링크드 리스트와 다르게 앞 뒤 노드를 연결하는 연산이 추가적으로 필요하다.

 

3)노드 탐색 연산

4)노드 삭제 연산

-더블 링크드 리스트의 삭제는 삭제할 노드의 2개의 포인터 다시 연결한 두개의 포인터로

 4개의 포인터를 다룬다.

 

5)노드 삽입 연산

-특정 구간의 노드를 삽입할 때 삽입할 노드의 이전노드와 다음노드를 연결한다.

 

6)노드 개수 세기 연산

2.더블 링크드 리스트 실습