[자료구조] #4_3 링크드 리스트

** 더블 링크드 리스트(Doubly Linked List)

- 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

 

클릭시 출처로 이동

 

---

class Node:
    def __init__(self, data, prev=None, next=None):
        self.prev = prev # 앞 노드와의 연결 정보
        self.data = data
        self.next = next

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

---

 

 

** 더블 링크드 리스트로 다양한 기능 구현

---

1) 검색

class Node:
    def __init__(self, data, prev=None, next=None):
        ...

class NodeMgmt:
    def __init__(self, data):
        ...

    def insert(self, data):
        ...

    def desc(self):
        ...
    
    def search_from_head(self, data): # 탐색 방향: 앞 -> 뒤
        if self.head == None:
            return False
    
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False
    
    def search_from_tail(self, data): # 탐색 방향: 앞 <- 뒤
        if self.head == None:
            return False
    
        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False

 

2) 삽입

    def insert_before(self, data, before_data): # 특정 노드 앞에 삽입
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.next = node
            return True

    def insert_after(self, data, after_data): # 특정 노드 뒤에 삽입
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.head
            while node.data != after_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            after_new = node.next
            new.next = after_new
            new.prev = node
            node.next = new
            if new.next == None:
                self.tail = new
            return True

    def insert(self, data): # 맨 뒤에 추가
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

---