[Python] LinkedList 구현하기

링크드 리스트(Linked List), 연결 리스트

떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

 

노드(Node) : 데이터 저장 단위 (데이터값, 포인터)로 구성

포인터(Pointer) : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

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)
        
# Node와 Node 연결하기 (포인터 활용)
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1


# 링크드 리스트로 데이터 추가하기
for index in range(3,10):
    add(index)


# 링크드 리스트 데이터 출력하기
node = head
while node.next:
    print(node.data)
    node = node.next

print(node.data)



        

 

장점

• 미리 데이터 공간을 할당하지 않아도 됨 (배열은 미리 할당해야함)

단점

• 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 좋지 않음
• 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
• 중간 데이터 삭제시 앞뒤 데이터의 연결을 재구성해야하는 부가적인 작업 필요

 

링크드 리스트 데이터 사이에 데이터를 추가

# 1과 2 사이에 1.5 넣기

node3 = Node(1.5)

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 NodeManagement:
    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.hdad == '':
            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

linkedlist1 = NodeManagement(0)
linkedlist1.desc() # 0

for data in range(1,10):
    linkedlist1.add(data)
linkedlist1.desc() # 0 ~ 9 출력

# head 지워보기
linkedlist1.delete(0)

linkedlist1.head # 아무것도 안나옴, 삭제 완료

linkedlist1.delete(4)

linkedlist1.desc() # 0 1 2 3 5 6 7 8 9 출력

 

 

다양한 링크드 리스크 구조

더블 링크드 리스크 (Doubly linked list), 이중 연결 리스트

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

class Node:
    def __init__(self, data, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next
        
class NodeManagement:
    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
            
    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
        
    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.prev = before_new
            new.next = node
            node.prev = new
            return True
 
 double_linked_list = NodeManagement(0)
 for data in range(1,10):
     double_linked_list.insert(data)
 
 double_linked_list.desc()
 
node_3 = double_linked_list.search_from_head(3)
if node_3:
    print(node_3.data)
else:
    print("No data")

node_3 = None
node_3 = double_linked_list.search_from_tail(3)
if node_3:
    print(node_3.data)
else:
    print("No data")
    
double_linked_list.insert_before(1.5, 2)
double_linked_list.desc() # 1과 2 사이에 1.5 인서트 됨