#6_ 파이썬으로 링크드 리스트(Linked list) 구현하기

안녕하세요.

이번 포스팅에서는 파이썬을 이용하여 링크드 리스트를 구현해보도록 하겠습니다.

1. 링크드 리스트(Linked list)란?

먼저 링크드 리스트가 무엇인지 간단히 살펴보도록 하겠습니다.

링크드 리스트는 위와 같이 세개의 형태를 가지고 있습니다.

그림에서 두번째, 양방향 연결 리스트는 *Prev 가 자신보다 앞의 요소를 가르키는 것입니다.

단순히 단방향 연결리스트를 구현하면 어떤 요소의 앞의 요소를 탐색하기 위해서 결국 다시 처음부터 검색을 진행해야 하는 일이 발생할 수 있기 때문에 수행능력이 보다 안좋을 수 있습니다.

이러한 것을 보완하기 위해 양방향 연결 리스트 및 환형 연결 리스트라는 개념이 있는데, 이들은 단방향 연결 리스트보다 구현하기는 상대적으로 어려울 수 있지만 앞에서 말씀 드린 상황과 같을 때 보다 효율적으로 수행될 수 있습니다.

2. 단방향 연결 리스트 구현하기

이번 포스팅에서는 단방향 연결 리스트만 구현해보도록 하겠습니다.

기본적으로 Node 클래스와 LinkedList 클래스를 구현하였습니다. Node 클래스는 단순히 새로운 노드를 만들어 리스트에 삽입할때 사용됩니다.

LinkedList는 insert, delete, search, print, listNum 의 함수를 가집니다.

insert는 사용자가 지정한 값을 리스트의 맨 뒤에 삽입시키며 delete는 첫 번째 요소를 출력하며 이를 삭제합니다. search는 사용자가 지정한 값이 리스트의 몇번째에 있는지 탐색합니다. print는 현재 리스트를 출력해주고 listNum은 리스트의 요소가 몇개인지 출력합니다.

이를 구현한 전체 파이썬 코드는 아래와 같습니다.

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self):
        HeadNode = Node("HEAD")
        self.head = HeadNode
        self.tail = HeadNode
        self.NumOfData = 0
        
    def insert(self,data):
        insertNode = Node(data)
        self.tail.next = insertNode
        self.tail = insertNode
        self.NumOfData += 1
        
    def delete(self):
        if self.NumOfData == 0:
            print("List is empty!")
            return False
        elif self.NumOfData == 1:
            delete_node = self.head.next
            self.head.next = None
            self.tail = self.head
            self.NumOfData -= 1
            print("리스트에서",delete_node.data,"데이터를 삭제하였습니다.")
            return delete_node.data
        else:
            delete_node = self.head.next
            self.head.next = self.head.next.next
            self.NumOfData -= 1
            print("리스트에서 ",delete_node.data,"데이터를 삭제하였습니다.")
            return delete_node.data
            
    def search(self,data):
        check = self.head
        for i in range(self.NumOfData):
            if check.next.data == data:
                print(data,"데이터는",i+1,"번째에 있습니다.")
                return None
            check = check.next
        print(data,"데이터는 리스트에 없습니다.")
        return None
        
    def listNum(self):
        print("현재 리스트에는",self.NumOfData,"개의 요소가 있습니다.")
        return self.NumOfData
    
    def printList(self):
        current = self.head
        if self.NumOfData == 0:
            print("List is empty!")
            return None
        print("HEAD::",end='')
        for i in range(self.NumOfData-1):
            print(current.next.data,"->",end='')
            current = current.next
        print(current.next.data)
    
list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.printList()
list.delete()
list.printList()
list.listNum()
list.insert(5)
list.insert(6)
list.insert(8)
list.insert(9)
list.insert(10)
list.printList()
list.listNum()
list.search(8)
list.search(7)

추가적으로 궁금한 사항이나 잘못된 점이 있으면 댓글을 남겨주세요 :)