자료구조) Linked List 구현하기

링크드 리스트를 구현하려면 꽤 생각해야 할 것이 많습니다.

하지만 차분히 하나씩 구현해보도록 합시다(나에게 하는 얘기)

 

1. Node 만들기 

링크드 리스트는 일단 데이터와 다음 주소를 가르키는 Node가 필요합니다. 

Node는 계속 반복해서 만들어질 것이기 때문에 클래스 형태로 만들어 줍니다

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

2. Node 연결해보기 

앞선 Node 클래스에 만들어 놓은 next로 노드를 연결해줍니다. 

head도 만들어줘야 하는데, linked list의 시작점을 알려줍니다. 

node_1 = Node(1)
node_2 = Node(2)
node_1.next = node_2
head = node_1

 

3. 노드를 맨 끝에 더하는 기능 : append

맨끝의 노드에 새로운 노드를 더하려면 next가 없는 node에 새 노드를 달아야 합니다.

그렇기 때문에 next가 있는지 없는지 확인하고, 있으면 현재 노드를 다음 노드(node.next)로 바꿔주는 것을 해줘야 합니다.

추가적으로, 혹시 head가 없을 수 있는 불상사를 예방하기 위해 head가 없으면 head로 지정하는 방어 코드도 만들어 줍시다. 

def append_node(data):
	if head : 
        node = head
        while node.next : #next가 없을때까지 찾는 코드
            node = node.next
        node.next = Node(data)
    else :
    	head = Node(data) # 헤드가 없을 경우의 방어코드

 

4. Linked List 확인해보기 

위의 것으로 노드를 왕창 만들고, linkedList에 잘 담겼는지 확인해볼 필요가 있습니다. 

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

node1 = Node(1)
head = node1

for i in range(2,10):
	append_node(i)
    
check_node(head)

잘 담겨 있는 것을 볼 수 있습니다. 

 

 

 

 

 

 

 

5. 중간에 새로운 요소 넣기

중간에 새로운 요소를 넣으려면 현재 노드를 기준으로 현재 노드의 next를 새 노드의 next로 넣고, 현재 노드의 next에 새 노드를 넣어주는 작업이 필요합니다.

def insertion(data, insertData): # 넣을 위치(앞선 노드), 넣을 데이터
	node = head
    while True: 
    	if node.data == data :
        	break
        else :
        	node = node.next
    #insertNode 만들어주기        
    insertNode = Node(insertData)
    
    insertNode.next = node.next
    node.next = insertNode

잘 적용되는 것을 볼 수있습니다. 

 

 

 

 

 

 

 

 

 

 

6. 요소 삭제 하기

요소를 삭제하려면 삭제하려는 현재 노드를 기준으로 앞선 노드를 기억하고, 앞선 노드의 next와 현재 노드의 next로 연결만 해주면 됩니다. 그런데 이때, 삭제하려는 node가 head 노드라면 head.next를 head로 지정해주는 것만 해주면 됩니다. 

def deletion(deletionData) :
    global head # 외부에 있는 head를 직접적으로 사용하기 위해서 global head를 넣어줌 
    if  head.data != deletionData :
        node = head
    #이전 값이랑 이후 값을 연결해줘야 하니 before_node를 만들어 놓음 
        before_node = head
        #이전 값이랑 이후 값을 연결해줘야 하니 before_node를 만들어 놓음 
        before_node = head
        while True :
            if node.data == deletionData:
                break
            else :
                before_node = node
                node = node.next

        #before_node의 next에 node.next를 연결해줌 
        before_node.next = node.next
    else :
        head = head.next

잘 작동하는 것을 볼 수 있습니다. 

 

7. 특정 요소가 linked list에 있는지 확인하기

앞서 이용했던 틀을 이용해주면 됩니다.

def search(searchData):
    node = head
    while True: 
        if node.data == searchData:
            print(True)
            break
        else :
            node = node.next

잘 잘동하네요

 

 

 

 

8. 클래스 형태로 링크드 리스트 만들어주기

함수로 따로따로 관리하는 것보다 클래스로 넣어서 만들어주면 조금더 객체지향적이면서 깔끔하고 읽기 쉬운 코드가 됩니다.

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 append(self, data):
        if self.head :
            node = self.head
            while node.next : 
                node = node.next
            node.next = Node(data)
        else :
            self.head = Node(data)
            

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

    def insertion(self, data, insertData): 
        node = self.head
        while True: 
            if node.data == data :
                break
            else :
                node = node.next
        insertNode = Node(insertData)
        insertNode.next = node.next
        node.next = insertNode

    def deletion(self, deletionData) :
        global head
        if  self.head.data != deletionData :
            node = self.head
            before_node = self.head
            while True :
                if node.data == deletionData:
                    break
                else :
                    before_node = node
                    node = node.next
            before_node.next = node.next
        else :
            self.head = self.head.next
            
    def search(self, searchData):
        node = self.head
        while True: 
            if node.data == searchData:
                print(True)
                break
            else :
                node = node.next

잘 작동하는 것을 볼 수 있네요ㅎㅎ

 

 

 

 

 

 

 

 

 

 

 

 

------

정말 길고 길었던 링크드 리스트가 어느정도 끝났네요

(플래그,, 아직 양방향 링크드 리스트가 남아있,,,, 나중에 시간 나면 해보는 걸로,,하핫)

그래도 제가 스스로 링크들 리스트를 생각하고 구현하게 되었다는 이 마인드가 얼마나 크게 저에게 자신감을 주는지 모릅니다.

링크드 리스트 탈출~~~ 성공~~~~~