[자료구조] Linked List,Double Linked List 구현 [python]

linked list

링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)

• 장점
  • 미리 데이터 공간을 미리 할당하지 않아도 됨
    • 배열은 미리 데이터 공간을 할당 해야 함
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
    

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

class LinkedList():
    def __init__(self,node):
        self.head = Node(node)

    def add(self,data):
        if self.head is None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

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

    def delete(self,data):
        if self.head==None:
            print("삭제할 노드가 없습니다.")
            return 
        node = self.head
        if node.data == data:
            self.head = node.next
            del node
        else:
            while node.next:
                temp = node.next
                if temp.data == data:
                    node.next = temp.next
                    del temp
                    return
                else:
                    node = temp         

    def search_node(self,data):
        node = self.head
        while node:
            if node.data == data:
                return node
            node = node.next

double linked list

7. 다양한 링크드 리스트 구조

• 더블 링크드 리스트(Doubly linked list) 기본 구조
  • 이중 연결 리스트라고도 함
  • 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
    

class Node:
    def __init__(self,data,prev=None,next=None):
        self.prev= prev
        self.data= data
        self.next= next
class DoubleLinkedList:
    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,prev=node)
            node.next = new
            self.tail = new

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

    def insert_before(self,next_data,new_data):
        if self.head is None:
            self.head = Node(new_data)
            self.tail = self.head
            return True
        else:
            node = self.tail
            while node.data != next_data:
                node = node.prev
                if node==None:
                    return False

            prev_node = node.prev
            new_node = Node(new_data,prev=prev_node,next=node)
            if prev_node:
                prev_node.next = new_node
            else:
                self.head = new_node
            node.prev = new_node
            return True

    def insert_after(self,before_data,new_data):
        if self.head is None:
            self.head = Node(new_data)
            self.tail = self.head
            return True
        else:
            node = self.head
            while node.data != before_data:
                node = node.next
                if node==None:
                    return False
            next_node = node.next
            new_node = Node(new_data,prev=node,next=next_node)
            if next_node:
                next_node.prev = new_node
            else:
                self.tail = new_node
            node.next = new_nod