파이썬 알고리즘, 자료구조 공부 - 이중 연결 리스트(doubly linked list)

지난 글에서 파이썬으로 연결리스트를 구성해봤습니다.(https://lsjsj92.tistory.com/461)

하지만 단순한 연결리스트는 단방향만 가기 때문에 양방향보다는 효율이 떨어집니다

그것을 보완하기 위해 양방향으로 갈 수 있는 연결 리스트를 구상했는데요

그게 이중 연결 리스트(doubly linked list) 입니다.

그림으로 보면 아래와 같은 구조입니다.

 

 

각 노드가 있고 노드안에 prev, next가 있어서 prev는 본인 노드 전의 지점을 가리킵니다.

next는 본인 노드 다음의 노드를 가리킵니다.

어렵지 않는 구조이죠

지난 번 포스팅에서 크게 달라지는 것은 없으며 prev 구조가 추가 되었습니다.

 

 

 

이게 끝입니다 ㅎㅎ 단순하죠?

하지만 삽입이나 삭제 같은 연산을 할 때는 좀 많이 달라집니다. 

한 번 볼까요?

 

 

먼저 일반적인 선언 방법입니다.

현재 노드는 A, B, D, E를 선언했고 C는 없습니다.

이제  C를 새로 넣으려고 합니다. 

 

 

아무래도 이중 연결 리스트다 보니 prev에는 이전의 노드를 그리고 next는 이후의 노드를 연결시켜주어야 합니다.

따라서 new_node를 하나 만든 후

node_P, node_T를 맨 처음 node_A를 가르키도록 합니다.

이후 데이터 값이 작아질 때까지 반복하며 node_P와 T를 반복하며 이동시켜줍니다.

node_P는 node_T보다 한 단계 전 노드를 가르키고 있습니다.

그리고 해당 노드 지점이 되면 new_node.next에 node_T를 넣고 new_node.prev에 node_P 정보를 넣습니다.

그리고 node_P.next에 new_node를 연결해야 완벅히 연결이 되겠죠? 또한, node_T.prev에 new_node 정보도 연결시켜 줍니다!

이중 연결 리스트(doubly linked list)는 이렇게 서로 양쪽을 구성해줘야 하기 때문에 조금 더 손이 많이 갑니다.

 

 

삭제도 마찬가지입니다.

만약 내가 삭제 하려는 노드를 발견하게 되면

삭제하려는 노드의 '이전 노드'는 삭제하려는 노드의 '다음 노드'에 대한 정보를 가져야 합니다.

삭제하려는 노드가 X라고 하고, 이전 노드는 X-1, 삭제하려는 노드 다음 노드는 X+1 이라고 가정하면

X-1.next 에는 X+1의 값이 있어야 하고, X+1.prev에는 X-1의 값을 가지고 있어야 합니다.

그리고 삭제하려는 노드가 있는지 계속 찾아봐야 하기 때문에 while문을 통해서 pre_node와 next_node, next_next_node를 활용해 계속 이동시켜 주면서 찾습니다.

 

 

결과는 위와 같이 됩니다.

오타가 있네요. 노드 D 삭제가 아니라 B 삭제입니다 ㅎㅎ..

 

이로서 파이썬으로 이중 연결 리스트를 구성해봤습니다.