[자료구조] Doubly Linked list

혼자서 책으로만 공부할때보다 훨씬 수월하게 이해가 되었으며, 이번 강의 역시 나에겐 꿀 강의였다.

갓고잉 선생님 : )

 

opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)

 

double linked list의 핵심은 이름과 같이 이중 연결 리스트로서, 단순 연결 리스트랑은 다르게,

노드의 앞뒤로 연결되어있다. 현재 노드와 이전 노드, 현재 노드와 다음 노드와 연결되어있게끔 구성이 되어있다.

단순 연결 리스트에서는, 데이터 필드와 다음 노드를 나타내는 링크 필드만 존재하였다면, 이중 연결 리스트에서는

이전 노드와, 다음 노드를 알려주는 링크 필드와 데이터 필드로 구성되어 있음을 아래에 그림을 통하여 확인할 수 있다.

 

https://opentutorials.org/module/1335/8940

장점 : 이것의 가장 큰 장점으로는, 양방향 연결이므로 노드를 탐색할 시 앞 뒤 양쪽으로 탐색이 가능하다.

위에서 언급한, 양방향 탐색의 가장 큰 장점은 특정 인덱스 위치의 엘리먼트를 가져올 시, 반복자를 이용해서 탐색할 때 드러난다.

단방향 연결 리스트는 다음 노드의 탐색만 가능했던 것에 비하여, 이중 연결 리스트의 경우 앞뒤로 탐색이 가능하다

상황에 따라 탐색의 방향이 변경되어야 한다면, 이중 연결 리스트를 사용한다.

 

단점 : 우선 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 한다. 이리하여, 메모리를 더 많이 사용하게 된다는 의미가 된다. 또 구현 자체도 조금 더 복잡해지는 단점이 있다. 하지만 이러한 단점에 비하여 장점이 크기 때문에, 현실에서 사용하는 연결 리스트는 대부분 이중 연결 리스트이다. 

 

 

 

https://opentutorials.org/module/1335/8940

위에 그림을 참조하면,  get(4) 번을 했을 때 순차적으로 탐색하는 것보다 뒤에서부터 찾는 것이 훨씬 효율적임을 알 수가 있다. 이전 노드를 참조하여 값을 알 수 있다면 훨씬 효율적이라는 것을 보여주는 그림이다.

 

강의를 보며 구현을 해보았고, 사실 혼자 구현해보라고 하면, 절대로 못했을 것 같은데 설명을 해주시는 거에 대한 이해가 된 것으로 스스로 위로해보며, 이번 소스코드도 git에 올려두었다.

 

생활코딩에서의 해주는 자료구조 강의가 이것으로 끝이라.. 너무 아쉽고 속상하다. 이젠 책과 돌아다니는 여러 강의 등을 통해 역량을 다져야겠다.

 

git address : github.com/egjeon/data-structure-doubly-linked-list