2. 파이썬 자료구조 링크드리스트

linked list

링크드리스트 - linked list

배열의 삽입과 추가가 어려운 것을 해결할 수 있다.

• 장점
  • 미리 데이터 공간을 할당하지 않아도 된다.
• 단점
  • 배열보다 데이터 공간을 많이 쓴다.
  • 저장공간이 비효율적이다.
  • 탐색이 어렵다. head부터 시작하기 때문에 원하는 데이터까지 접근속도가 느리다.
  • 중간 데이터 삭제 시, 앞뒤 데이터 연결을 재구성 해야 한다.

클래스를 사용하여 구현한다.

class Node :
    def __init__(self,data,next=None):
        self.data=data
        self.next=next
def add(data):
    node=head
    while node.next:
        node=node.next
    node.next=Node(data)

node1=Node(1)
head=node1
for index in range(2,10):
    add(index)

node=head
while node:
    print(node.data)
    node=node.next

데이터를 삽입할 때는 다음과 같다.

node=head
search=True
while search :
    if node.data==1 :
        search=False
    else :
        node=node.next
node_next=node.next
node.next=node3
node3.next=node_next

파이썬 객체지향 프로그래밍으로 링크드 리스트를 구현한다

class Node : 
    def __init__(self,data,next=None) : 
        self.data = data
        self.next= next
        
class NodeMgmt:
    def __init__(self,data):
        self.head=Node(data)
    
    def add(self,data):
        if self.head =='' :
            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

linkedlist1=NodeMgmt(0)
linkedlist1.desc()

for data in range(1,10) :
    linkedlist1.add(data)
linkedlist1.desc()

특정 노드를 삭제하는 순서
1. head 삭제
2. 마지막 노드 삭제
3. 중간 노드 삭제

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

class NodeMgmt : 
    def __init__(self, data) : 
        self.head=Node(data)
    def add(self,data) : 
        if self.head=='' : 
            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 =='' :
            print("no Node.")
            return
        
        if self.head.data == data : 
            temp = self.head
            self.head=self.head.next
            del temp
        else : 
            node = self.head
            while node.next : 
                if node.next.data == data : 
                    temp = node.next
                    node.next=node.next.next
                    del temp
                else :
                    node=node.next

더블링크드리스트 (double linkedlist)
: head 와 tail 모두에서 탐색을 시작할 수 있다.

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

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