연결리스트 - 이중 연결 리스트

안녕하세요 Dibrary입니다.

앞에서 단일연결 리스트를 보셨다면, '역순으로도 확인할 수 있으면 좋겠다~' 싶은 생각이 드셨을 수 있는데, 이 기능도 같이 구현한 것이 이중연결 리스트 입니다.

2022.05.17 - [자료구조] - 연결리스트 - 단순 연결 리스트

 

이렇게 양방향 화살표인 셈이죠. 근데, 사실 '개념'은 이래도, 양방향으로는 각 Node별로 앞, 뒤가 나뉘어져 있습니다.

따라서, 아래와 같이 표현하는 게 좀 더 정확합니다.

그래도 앞에서 뒤로, 뒤에서 앞으로 올 수 있다는 사실은 변함이 없습니다.

 

---

이번에도 파이썬으로 코드 구현을 해보겠습니다. 먼저 노드만을 만들어 보고 기본 개념 확인을 해보겠습니다.

A와 B와 C라는 노드를 만들고, A <-> B <-> C 이렇게 연결 했습니다.

A부터 C까지 값을 확인해 볼 수 도 있고, C부터 A까지 역순으로도 값을 확인할 수 있습니다.

 

---

 

그러면 이제 추가와 삭제가 가능한 '자료구조' 형태로 만들어 보겠습니다.

코드 동작 결과는 아래와 같습니다.
임의로 A와 B 두 개만 넣어보았고, A-> B, B-> A 값을 확인해 보았습니다.

 

---

코드를 살펴보면

1. 생성자 부분에서 head, tail 속성 만듦.

이게 무슨 말인고 하니, 처음에 만들때 값이 주어지지도 않았는데 리스트를 구성할 수는 없잖아요? 그래서 임의로 앞부분과 끝부분을 가리킬 변수를 head, tail이라고 만들고 head -> tail 로 연결만 해 놓은 겁니다. 

 

2. 지정 노드 앞에 값 넣기

node라고 넣는 객체 앞에 추가를 하는 코드입니다.

당연히 노드가 하나 추가 되었으니 전체 리스트 길이인 self.size도 +1을 해 줍니다.

 

3. 지정 노드 뒤에 값 넣기

위에서 넣은 것과 정 반대 방향으로만 해 주시면 됩니다. (prev와 next_node를 잘 바꾸면 되죠)

 

4. 노드 삭제

삭제는 간단합니다. 해당 노드를 지우는 게 아니라, 연결만 무시해버린다고 생각하시면 됩니다.

그래서 삭제하고자 하는 대상노드의 앞과 대상 노드 뒤를 연결 해 주시고 리스트 길이를 -1 해 주시면 됩니다.