[Python] Linked List (연결 리스트)

1. 링크드 리스트란?

 

출처 : https://en.wikipedia.org/wiki/Linked_list

연결 리스트라고도 하는 linked list는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

링크드 리스트 기본 구조

• 노드(Node) : 데이터 저장 단위(데이터 값, 포인터)로 구성
• 포인터(Pointer) : 각 노드 안에서, 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간

 

2. 구현

Node 구현

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

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

 

링크드 리스트 구현

class Node:
	def __init__(self,data,next=None):
    	self.data=data
        self.next=next
        
    def add(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 search_node(self, data):
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

[1]->[3]->[5]->[8]을 [1]->[3]->[5]->[7]->[8]로 만들고 싶다면

1. new_node=Node(7)

2. [5]를 찾고 ( node=seact_node(5) )

3. node_next=node.next

   node.next=new_node

   new.node = node. next

[5]가 가리키는 노드를 7이 가리키게 하고, 다시 5는 7을 가리키게 하면 된다.

삭제

def delete(self, data):
        if self.head == '':
            print ("해당 값을 가진 노드가 없습니다.")
            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
                    return
                else:
                    node = node.next

 

현재 노드에 삭제하고자 하는 다음 노드를 연결해주면 된다.

정리

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgm:
    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 ("해당 값을 가진 노드가 없습니다.")
            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
                    return
                else:
                    node = node.next

 

3. 링크드 리스트의 장단점

장점

• 미리 데이터 공간을 할당하지 않아도 된다.

단점

• 연결을 위한 별도 공간이 필요하므로 저장 공간의 효율이 높지 않다.
• 접근 속도가 느리다.