자료구조 6강-2 | Linked List | 숙명여대 학점교류

숙명여대 학점교류로 듣는 자료구조

day 6. 2021.12.29. 수요일

 

 

---

Doubly linked list

problem of SLL

when deleting a node, it should know a prior node to connect the list

DLL

each node had both before and after nodes

easy to delete / insert a node

fields 

data

left link

right link

applications

binary tree

 

DLL Insert

class Node:
    def __init__(self, data):
        self.data = data
        self.llink = None
        self.rlink = None
    def insert(self, prev, item): # append after prve
        if not self.head: return
        node = Node(item) # insert to the frot if not prev
        if not prev:
            node.rlink = self.head
            self.head = node
            return
        else:
            node.rlink = prev.rlink
            if prev.rlink: prev.rlink.llink = node
            prev.rlink = node
            node.llink = prev
            if not node.rlink: self.rear = node

 

노드의 존재 여부에 따라 달라지는 것

양방향 연결 리스트이므로 

 

노드의 rlink가 없다면, 마지막 노드가 되는 것이다. 

rear가 가리키도록 한다. 

 

DDL Delete

    def delete(self, item):
        if not self.head:
            print("List Empty")
            return
        node = self.find(item)
        if not node:
            print("Not Found")
            return
        if node.llink:
            node.llink.rlink=node.rlink
            if node.rlink:
                node.rlink.llink = node.llink
            print("Node is deleted. prev exist")
        else:
            if self.head == node:
                print("head is deleted")
            self.head = node.rlink
            if node.rlink:
                node.rlink.llink = None
        if self.rear == node: 
            self.rear = node.llink
        del node