[자료구조] 더블 링크드 리스트(Doubly linked list)

더블 링크드 리스트(Doubly linked list) 기본 구조

• 이중 연결 리스트라고도 함
• 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
  

  

# Node 데이터 생성
class Node:
    def __init__(self, data, prev=None, next=None):
        # 현재 노드의 이전 노드
        self.prev = prev
        # 현재 노드 데이터
        self.data = data
        # 다음 노드
        self.next = next

# Node 데이터 관리함수
class NodeMgmt:
    # 데이터 초기화
    def __init__(self, data):
        # 최초 data로 head Node를 생성
        self.head = Node(data)
        # tail data 데이터에 head Node를 지정 최초에는 다음 데이터가 없으므로 head와 tail이 동일함
        self.tail = self.head

    # 특정 숫자(before_data)인 Node 앞에 Node 데이터를 추가하는 함수
    def insert_before(self, data, before_data):
        # head data가 없으면 데이터로 head Node 생성
        if self.head == None:
            self.head = Node(data)
            return True
        # head Node가 있으면
        else:
            # node에 tail Node를 대입
            node = self.tail
            # 특정 숫자(before_data)를 찾을 때까지 가장 마지막 데이터 부터 앞으로 순회
            while node.data != before_data:
                node = node.prev
                # node.prev 가 없으면 False 처리
                if node == None:
                    return False
            ## 새로 추가될 데이터 Node 생성
            new = Node(data)
            ## node.prev Node를 새로 추가될 Node 의 prev Node 로 지정하기 위해 임시 저장
            before_new = node.prev
            ## 특정숫자(before_data) node의 prev Node의 next Node를 새로 추가될 Node로 지정
            before_new.next = new
            ## 새로 추가될 Node의 next node를 특정숫저(before_data) node로 지정
            new.next = node
            return True

    # 특정 숫자(after_data)인 Node 뒤에 Node 데이터를 추가하는 함수
    def insert_after(self, data, after_data):
        # head data가 없으면 데이터로 head Node 생성
        if self.head == None:
            self.head = Node(data)
            return True
        # head Node가 있으면
        else:
            # node에 head Node를 대입
            node = self.head
            # 특정 숫자(after_data)를 찾을 때까지 가장 첫 데이터 부터 뒤로 순회
            while node.data != after_data:
                node = node.next
                 # node.next 가 없으면 False 처리
                if node == None:
                    return False
            ## 새로 추가될 데이터 Node 생성
            new = Node(data)
            ## node.next Node를 새로 추가될 Node의 next Node 로 지정하기 위해 임시 저장
            after_new = node.next
            ## 새로 추가될 Node의 next Node를 특정 숫자(after_data) next Node로 지정
            new.next = after_new
            ## 새로 추가될 Node의 prev Node를 특정 숫자(after_data) Node로 지정
            new.prev = node
            ## 특정 숫자(after_data) Node의 next Node를 새로 추가될 데이터 Node로 지정
            node.next = new
            ## 새로 추가된 데이터 Node 가 가장 마지막이면 self.tail 에 새로 추가된 데이터 Node를 지정
            if new.next == None:
                self.tail = new
            return True

    # 일반적인 Node 데이터 추가 함수
    def insert(self, data):
        # head data가 없으면 데이터로 head Node 생성
        if self.head == None:
            self.head = Node(data)
        # head Node가 있으면
        else:
            node = self.head
            ## 가장 마지막 Node를 찾을때까지 순회
            while node.next:
                node = node.next
            ## 새로운 Node 생성
            new = Node(data)
            ## 가장 마지막 Node next Node 에 새로운 Node 지정
            node.next = new
            ## 새로운 Node prev Node에 가장 마지막 Node 지정
            new.prev = node
            ## self.tail Node에 새로운 Node 지정
            self.tail = new

    # 링크드리스트 내역 조회
    def desc(self):
        node = self.head
        ## head Node 부터 모든 Node를 순회하며 출력
        while node:
            print(node.data)
            node = node.next

연슴문제 1. 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고, 테스트해보기

• 더블 링크드 리스트의 tail 에서부터 뒤로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기
• 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 2인 노드 앞에 1.5 데이터 값을 가진 노드를 추가해보기

double_linked_list = NodeMgmt(0)
for data in range(1, 10):
    double_linked_list.insert(data)
double_linked_list.desc()

double_linked_list.insert_before(1.5, 2)
double_linked_list.desc()

0
1
1.5
2
3
4
5
6
7
8
9

연습문제 2. 노드 데이터가 특정 숫자인 노드 뒤에 데이터를 추가하는 함수를 만들고, 테스트해보기

• 더블 링크드 리스트의 head 에서부터 다음으로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기
• 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 1인 노드 다음에 1.7 데이터 값을 가진 노드를 추가해보기

node_mgmt = NodeMgmt(0)
for index in range(1,10):
    node_mgmt.insert(index)

node_mgmt.insert_after(10, 9)
node_mgmt.desc()

0
1
2
3
4
5
6
7
8
9
10