[자료구조]링크드 리스트(Linked list)

링크드 리스트에 대해서 살펴보겠습니다.

링크드 리스트는 연결 리스트라고도 하는데요.

데이터의 연결을 링크로 하는 방식으로 

쉽게 구현할 수 있는 배열 같은 경우 연결된 공간에 순차적으로 데이터를 나열했다면 

링크드 리스트는 데이터를 화살표로 연결해서 이어나가는 구조를 가집니다.

따라서 데이터가 떨어져 있어도 화살표로 연결이 가능합니다.

각 데이터의 구성은 다음과 같습니다.

 

• 노드(Node) : 데이터 저장 단위(데이터값, 포인터)
• 포인터(Pointer) : 각 노드에서 다음이나 이전의 노드의 연결 정보를 넣은 공간

그림으로 보면 A,B,C 가 데이터값, 점이 그려진 공간이 포인터가 됩니다. 

구조 형성을 위해 공간을 미리 확보하지 않아도 되고 중간 지점에 추가 삭제가 가능하고 빠르다는 장점이 있지만

각 노드마다 연결을 위한 별도의 공간이 필요해서

효율이 좋지 못하고 연결 정보를 찾는 시간이 필요해 접근 속도가 느립니다(O(n) 소요).

중간 데이터를 삭제하면 노드 연결을 다시 해줘야 하는 작업이 필요한 단점이 있습니다.

즉, 복잡합니다. 그럼에도 링크드 리스트만의 장점이 특화되어 있어서 자주 쓰이는 편입니다.

 

이제 파이썬으로 구현을 해보겠습니다.

구성해야 하는 건 Node와 Node 추가,삭제 방법 그리고 화살표 연결 방법을 정해주어야 합니다.

 

링크드 리스트 구현

Node는 데이터와 포인터로 이루어져 있습니다.

그렇지만 포인터는 따로 지정을 하지 않고 데이터를 가져올 때마다 포인터는 자동으로 생성되어야 합니다.

 

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

이제 Node를 만들어서 링크드 리스트로 데이터 추가합시다.

Node는 항상 포인터를 가지고 있으니 포인터가 더이상 존재하지 않을때까지 계속해서 추가합니다.

def add(data):
	node = head
    while node.pointer:
    	node = node.pointer
    node.pointer = Node(data)
    
# 추가
node1 = Node(1)
head = node1
for idx in range(2,10):   #Node(1)은 이미 존재하므로 range(2,10)
    add(idx)

잘 구현이 되었는지 출력을 해봅시다.

def output(node=head):
    while node:
    	print(node.data)
        node = node.pointer
    
output()
1
2
3
4
5
6
7
8
9

기본 틀은 완성했고 링크드 리스트의 장점인 노드 중간에 추가, 삭제를 구현해보겠습니다.

기존 노드에서 추가를 하려면 추가할 곳의 이전 포인터를 변경해주고 추가 포인터는 이후 데이터를 가르키도록 합니다. 

그래서 이전 데이터를 찾아내 포인터를 변경합니다.

node2 = Node(1.5)    #추가할 node

node = head
search = True
while search:
    if node.data == 1:     #이전 찾기
        search = False
    else:
        node = node.pointer

node_pointer = node.pointer      # 변경 전의 값 필요
node.pointer = node2          # 이전 pointer 바꿈
node2.pointer = node_pointer     # 이후 pointer 바꿈(이전 pointer가 이후 데이터를 가리킴)

output()
1
1.5
2
3
4
5
6
7
8
9

노드 중간을 지워봅시다.

def delete(data,head=head):
    node = head
    if node.data == data:
        temp_save = node
        head = node.pointer
        del temp_save
    else:
        
        while node.pointer:
            if node.pointer.data == data:
                temp_save = node.pointer
                node.pointer = node.pointer.pointer
                del temp_save
                return
            else:
                node = node.pointer

output()
1
1.5
2
3
4
5
6
7
8
9

delete(1.5)
output()
1
2
3
4
5
6
7
8
9

 

이렇게 하면 head는 안 지워집니다. 그 이유는 head가 전역변수라서 함수 안에서 수정이 불가능합니다.

 

마지막으로 링크드 리스트를 하나의 객체로 만들어서 관리가 편하고 head도 지울 수 있게 하겠습니다.

class Node:
    def __init__(self, data, pointer=None):
        self.data = data
        self.pointer = pointer
    
class NodeMg:
    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.pointer:
                node = node.pointer
            node.pointer = Node(data)
        
    def output(self):
        node = self.head
        while node:
            print (node.data)
            node = node.pointer
    
    def delete(self, data):
        if self.head == '':
            print ("No Node")
            return
        
        if self.head.data == data:
            temp_save = self.head
            self.head = self.head.pointer
            del temp_save
        else:
            node = self.head
            while node.pointer:
                if node.pointer.data == data:
                    temp_save = node.pointer
                    node.next = node.pointer.pointer
                    del temp_save
                    return
                else:
                    node = node.pointer
     def search_node(self,data):
         node = self.head
         while node:
             if node.data ==data:
                 return node
             else:
                 node = node.pointer

head가 지워지는지 확인해보겠습니다. 

linked = NodeMg(0)
linked.output()
0

linked.head.data
0
linked.delete(0)
linked.head.data

head를 지워서 'NoneType'이 되었습니다.

 

조금 복잡한 과정을 거쳤지만 링크드 리스트를 구현해봤습니다.

이상으로 포스팅을 마치겠습니다.