[Python] 이중 연결 리스트(Doubly linked list)

해당 책의 Chapter 05 응용예제 02번의 문제임을 참고 부탁드립니다.

이 책을 쓰신 우재남 저자는 굉장한 트와이스 팬이십니다. 이유는 아래를 보면 아실 것입니다.

예제 설명

다음과 같이 양방향으로 링크가 연결되는 이중 연결 리스트를 만든다. 헤드부터 차례대로 출력한 후 이어서 마지막 노드부터 거꾸로 다시 출력해보자.

(저작권의 문제로 다른 이미지로 대체합니다)

[출처:https://opentutorials.org/module/1335/8940]

위 블로그에는 자료 구조에 대한 설명이 정말 잘 나와 있으니 저처럼 알고리즘 공부 중 습관성 '에엥?😑😐' 하시는 분들이라면 영상까지 꼭 보시는 걸 추천드려요!

실행 결과

우리가 원하는 출력값은 아래와 같습니다.

정방향 --> 다현 정연 쯔위 사나 지효
역방향 --> 지효 사나 쯔위 정연 다현

제가 푼 방법

1. 이중 연결 리스트를 만들기 이전에, 단순 연결 리스트(singly linked list)가 필요하겠다고 생각해서 그 코드를 그대로 가져옴

# 일반 단순 연결 리스트의 생성 함수 완성
# 단순 연결 리스트 생성

## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.link = None

def printNodes(start):                  # 매개변수로 시작 노드를 전달 받음
    current = start                     # 전달 받은 시작 노드를 현재 노드로 지정
    if current == None:                 # 노드에 데이터가 하나도 없는 연결 리스트인 경우 반환
        return
    print(current.data, end=' ')        # 현재 노드 출력
    while current.link != None:         # 노드의 링크가 빌 때까지 출력
        current = current.link
        print(current.data, end=' ')
    print()
    
    
## 전역 변수 선언 부분 ##
memory = []                             # 생성할 노드 저장할 메모리 준비
head, current, pre = None, None, None   # 시작 노드, 현재 노드, 이전 노드에 사용할 변수 준비
dataArray = ['다현', '정연', '쯔위', '사나', '지효']


## 메인 코드 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]            # 첫 번째 노드 생성
    head = node
    memory.append(node)

    for data in dataArray[1:]:          # 두 번째 이후 노드
        pre = node                      # 현재 노드를 이전 노드로 저장함
        node = Node()                   # 새 노드 생성
        node.data = data                # 노드에 데이터를 넣음
        pre.link = node                 # 이전 노드 링크에 새 노드 대입
        memory.append(node)             # 새 노드를 메모리에 넣음

    printNodes(head)                    # 생성이 완료된 단순 연결 리스트 출력

2. 정방향 —>... 으로 뽑히는 data는 기존 정의내린 printNodes 로 가능했기에 아 여기에 역방향 출력을 넣어주면 되겠다라고 생각함

3. 잠시 뇌정지 와서 해당 자료를 찾아봄

doubly linked list의 핵심은 노드와 노드가 서로 연결되어 있다는 점입니다. 아래 그림을 보면 단순 연결 리스트(linked list)와는 다르게 노드가 이전 노드(previous)와 다음 노드(next)로 구성되어 있습니다.

출처는 위의 링크와 같습니다.

여기서 단순 link가 아니라 next(정방향 연결)를 위한 link, previous(역방향 연결)를 위한 link가 필요하겠다 싶은 생각이 들었음.

4. 그래서 클래스 재정의

class Node():
	self.data = None # 기존 data
	self.next = None # 다음 링크로 가기 위한 링크
	self.prev = None # 이전 링크로 가기 위한 링크

5. printNodes() 함수 재정의

def printNodes(start):                  
    current = start
    if current == None:
        return
    print('정방향 -->', current.data, end=' ')        
    while current.next != None:
        current = current.next
        print(current.data, end=' ')
    print()
    print('역방향 -->', current.data, end=' ')        
    while current.prev != None:
        current = current.prev
        print(current.data, end=' ')
    print()

함수를 이렇게 만들어주고 메인 코드 선언 부분에서 prev와 next 방향을 잘 알려줘야 제대로 수행이 가능해짐

6. 메인 코드 부분 재선언

## 메인 코드 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]            # 첫 번째 노드 생성
    head = node
    memory.append(node)

    for data in dataArray[1:]:          # 두 번째 이후 노드
        pre = node                      # 현재 노드를 이전 노드로 저장함
        node = Node()                   # 새 노드 생성
        node.data = data                # 노드에 데이터를 넣음
        pre.next = node                 # 이전 노드 링크에 새 노드 대입
        node.prev = pre
        memory.append(node)             # 새 노드를 메모리에 넣음

    printNodes(head)                    # 생성이 완료된 단순 연결 리스트 출력

• pre.next = node
  이전 노드 링크에 다음 노드를 대입한다
• node.prev = pre
  노드의 prev란 링크에 이전 노드를 대입시켜줘서 이전 노드로 이동하게 만들어준다.

어려웠습니다. 처음엔 물론 상상이 잘 안 갔는데, 일단 singly linked list를 먼저 떠올렸다는 점에서 반은 성공이었던 것 같습니다.

그리고 class를 다시 선언해야하나 헷갈려서 자료구조 자료를 찾아보고, 확신이 생겨서 고치게 되었습니다.

전체 코드

# 2. 응용예제02 이중 연결 리스트 구현하기
# Doubly linked list (이중 연결 리스트)


## 클래스와 함수 선언 부분 ##
class Node():
    def __init__(self):
        self.data = None
        self.prev = None
        self.next = None

def printNodes(start):                  
    current = start
    if current == None:
        return
    print('정방향 -->', current.data, end=' ')        
    while current.next != None:
        current = current.next
        print(current.data, end=' ')
    print()
    print('역방향 -->', current.data, end=' ')        
    while current.prev != None:
        current = current.prev
        print(current.data, end=' ')
    print()

## 전역 변수 선언 부분 ##
memory = []                             # 생성할 노드 저장할 메모리 준비
head, current, pre = None, None, None   # 시작 노드, 현재 노드, 이전 노드에 사용할 변수 준비
dataArray = ['다현', '정연', '쯔위', '사나', '지효']

## 메인 코드 부분 ##
if __name__ == "__main__":

    node = Node()
    node.data = dataArray[0]            # 첫 번째 노드 생성
    head = node
    memory.append(node)

    for data in dataArray[1:]:          # 두 번째 이후 노드
        pre = node                      # 현재 노드를 이전 노드로 저장함
        node = Node()                   # 새 노드 생성
        node.data = data                # 노드에 데이터를 넣음
        pre.next = node                 # 이전 노드 링크에 새 노드 대입
        node.prev = pre
        memory.append(node)             # 새 노드를 메모리에 넣음

    printNodes(head)                    # 생성이 완료된 단순 연결 리스트 출력

오류가 있다면 말씀해주세요!