자료구조발행일 2023. 5. 12.원본 https://blog.naver.com/jword_/223100442998 ↗

파이썬에 연결리스트(linked list)가 없는 이유

파이썬에 연결리스트(linked list)가 없는 이유 — #파이썬연결리스트 #파이썬linkedlist #연결리스트 #링크드리스트 AI스쿨 msa기반 java 백엔드 코스 중에...

#자료구조#Naver Blog

#파이썬연결리스트 #파이썬linkedlist #연결리스트 #링크드리스트

AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다

파이썬에 연결리스트가 없는 이유

이전글을 통해 파이썬에 배열이 없는 이유를 알아보았고, 클래스로 직접 구현하는 방법도 함께 알아보았습니다. 오늘은 파이썬에 연결리스트가 없는 이유를 알아보고 클래스로 함께 구현해봅시다!

우선 순수 연결리스트의 특징은 인덱스가 존재하지 않습니다. 하지만, 파이썬의 리스트는 인덱스로 해당 값에 대한 접근 및 수정, 삭제 모두 가능합니다. 배열을 설명할때 파이썬은 배열과 연결리스트의 장점만을 뽑아서 만든 제 3의 자료구조라고 한점을 기억해주세요.

거기다 연결리스트는 노드로 구성되어있어 두 가지 정보를 저장해야만 합니다. 현재 노드가 가지고 있는 데이터와 다음 노드에 대한 정보를 모든 노드가 저장하고 있습니다.

인덱스가 없으면서 다음 값에 정보를 가지고 있는 리스트라... 처음 접하는 분들에게는 매우 난감한 구조가 아닌가 생각됩니다. 직접 본적이 없어서 구현하기가 힘든 것도 있습니다.

하지만, 그림을 그려가며 저와 함께 파이썬 클래스로 연결리스트(링크드 리스트)를 구현해보시면 금방 감이 잡히리라 생각됩니다.

링크드 리스트 구조 만들기

노드와 리스트

링크드 리스트는 리스트외에 따로 노드를 생성하여 정보를 저장해 줘야합니다. 우선적으로 다음과 같은 구조를 기대해 볼 수 있습니다.

class Node: def \_\_init\_\_(self, data): passclass LinkedList: def \_\_init\_\_(self): pass

Node클래스는 현재 데이터의 데이터 값과 다음 데이터에 대한 정보와 이전 데이터에 대한 정보를 저장합니다. 그리고 링크드 리스트는 현재 노드의 위치와 가장 첫번째 노드의 위치, 마지막 값은 LAST라고 하는 None값이 들어있는 노드를 생성하겠습니다..LAST의 경우에는 항상 마지막 값이 되며 삭제되지도 수정되지도 않습니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST

이렇게 구조를 짜는 이유는 처음부터 링크드 리스트를 바로 구현하기 어렵기 때문입니다. 보기 쉬운 형태로 만든 후, 편의상 만든 값들을 전부 치환해 줄 예정입니다. (아래로 내려가시면 이해하기 쉬워요)

처음 상태는 LAST만 존재하는 상태기에 self.current와 self.head에 self.LAST 값을 넣어 두었습니다.

링크드 리스트의 기능들

이전글을 통해 자료구조의 전체 기능을 한번 다뤄봤습니다. 여기서 링크드 리스트의 기능을 간략하게 다시한번 언급하고 넘어가겠습니다.

링크드 리스트는 현재 값을 읽고, 수정하고, 삭제하고, 옆칸에 값을 추가하고, 이동하고, 맨처음으로 이동한다. 위기능들을 구현하기 위한 함수의 전체 틀만 클래스에 함수로 추가해줍니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def move\_next(self): pass def get(self): pass def modify(self, value): pass def add(self, value): pass def delete(self): pass def move\_front(self): pass

이제 차례대로 하나씩 구현해보겠습니다.

다음 노드로 이동
move\_next(self)

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def move\_next(self): if self.current is None: return self.current = self.current.next

현재값이 None인 경우는 아무것도 들어가있지 않은 상태, 맨끝값인 경우가 됩니다. 이때는 다음 값에 대한 정보가 없으므로 ㄱㄷ셔구하여 동작하지 않도록 구현합니다. 값이 들어있는 상태라면 위치를 현재의 다음으로 옮깁니다.

현재 노드값 읽기
get(self)

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def get(self): if self.current is None: return None return self.current.data

현재 값이 None일때는 None을 return하고 값이 존재한다면 현재 값에 대한 정보를 return해주면 됩니다.

현재 노드값 수정
modify(self, value)

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def modify(self, value): if self.current is None: return self.current.data = value

현재값이 None이라면 수정해서는 안되며, 값이 존재한다면 외부 입력값으로 값을 변경합니다.

맨 앞으로 이동
move\_front

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def move\_front(self): self.current = self.head

현재 위치를 self.head로 옮겨줍니다.

기능 구현 심화

자 여기까지는 매우 간단하게 구현이 가능합니다. 이제 노드를 추가하거나, 노드를 삭제하는 경우만 남았습니다. 다양한 경우가 존재하기 때문에 여러가지 경우의 수를 따져 봐야 합니다.

경우의 수를 따지는 이유는 노드를 삭제나 추가 할 때마다 현재 노드와 다음 노드를 계속 이어줘야 하기 때문입니다. 우선 삭제에 대한 경우의 수와 추가의 경우의 수를 따져가며 구현을 해보겠습니다.

노드 삭제

노드 삭제의 경우에 현재 노드의 이전 노드와 현재 노드의 다음 노드를 서로 이어줘야 합니다. 아래 코드에서는 Y를 현재노드, X를 이전 노드, Z를 다음 노드로 규정하였습니다.

# case 1

가장 처음 생각해볼 수 잇는 경우의 수는 self.LAST 빈 노드만 있는 경우입니다. 이때는 값을 삭제하면 안되므로 return 합니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def delete(self): # 현재노드 Y = self.current # 이전노드 X = Y.prev # 다음노드 Z = Y.next # case 1 # L # ^ = current pointer if Y is self.LAST: return

# CASE2

다음으로 생각해 볼 수 있는 경우의 수는 가장 일반적인 상황입니다. X, Y, Z 노드가 모두 존재하고, Y를 삭제하는 경우입니다. 이때는 X와 Z를 이어줘야 합니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def delete(self): Y = self.current X = Y.prev Z = Y.next # case 1 if Y is self.LAST: return # case 2 # X -> Y - > Z -> L # ^ # X -> Z -> L # ^ X.next = Z Z.prev = X self.current = Z

X의 다음값을 Z로, Z의 이전값을 X로 이어줍니다.

# case 3

3번째 케이스는 현재 값의 다음값이 self.LAST (= None)인 경우를 따져봐야 합니다. 2번째 케이스에서 구현된 코드와 동일하게 적용되어 따로 작성할 코드는 없습니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def delete(self): Y = self.current X = Y.prev Z = Y.next # case 1 if Y is self.LAST: return # case 2 X.next = Z Z.prev = X self.current = Z # 3 # X -> Y -> L(Z) # ^ # X -> L(Z) # ^

case 4#

4번째 케이스는 현재 값이 가장 앞쪽 self.head에 위치한 경우입니다. 이때는 이전 값이 존재하지 않으므로 기존에 작성한 코드에서 조건 처리를 해줘야합니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def delete(self): Y = self.current X = Y.prev Z = Y.next # case 1 if Y is self.LAST: return # case 2, 3 + 4 if Y is not self.head: X.next = Z else: self.head = Z Z.prev = X self.current = Z # case 4 # Y -> Z -> L(Z) # ^ # Z -> L(Z) # ^

Y, 즉 현재 위치가 head가 아닐때만 이전 노드와 다음 노드를 연결하고, 현재 위치가 해드일 경우는 연결하지 않습니다. 현재 위치가 해드일 경우 head 노드에 대한 재설정도 해줘야 하기 때문에 self.head = Z로 둡니다. 이경우 X값이 존재하지 않는 None이기 때문에 Z.prev = X로 두어도 무방합니다.

노드 추가

노드 추가의 경우도 경우의수를 따져봐야합니다. 구현은 새로운 노드를 추가하게 되면 현재위치의 노드를 새로운 노드 다음 노드로 구현하고 현재 위치를 새로운 노드로 변경합니다. 그림보시면 이해하기 편할겁니다!

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def add(self, value): # 새로운 노드 A = Node(value) # 현재 위치 Y = self.current # 이전 위치 X = Y.prev # 다음 위치 Z = Y.next

케이스를 나누기전에 우선 delete함수와 동일하게 X, Y, Z를 각각 이전, 현재, 다음위치로 지정해줍니다. 추가로 add로 새로운 노드값을 넣을 것이기 때문에 A = Node(value)를 지정해 주었습니다. 역시나 기호로 나타내는것은 편의를 위해섭니다!

case 1#

가장 기본이 되는 케이스입니다. 이전노드와 현재노드의 위치 정보를 새로운 노드에 연결해주어야합니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def add(self, value): A = Node(value) Y = self.current X = Y.prev Z = Y.next # case 1 # X -> Y -> Z -> L # ^ = current pointer # X -> A -> Y -> Z -> L # ^ A.prev = X A.next = Y X.next = A Y.prev = A self.current = A

추가된 노드의 이전 값과 다음값을 X, Y로 연결해주고, 기존 X, Y의 다음값과 이전값을 A로 연결해주면 됩니다.

case 2#

X값이 존재하지않고, Y(=현재)가 self.head인 case입니다. delete의 경우의 수와 동일합니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def add(self, value): A = Node(value) Y = self.current X = Y.prev Z = Y.next # case 1 A.prev = X A.next = Y if Y is not self.head: X.next = A else: self.head = A Y.prev = A self.current = A # case 2 # Y -> Z -> L # ^ # A -> Y -> Z -> L # ^

이경우 X값이 존재하지 않기 때문에 X.next = A로 두는것이 바람직하지 않습니다. 조건에 현재값(Y)이 self.head가 아닌경우에만 X.next = A 를 하도록 구현합니다. Y가 self.head에 있는 경우에는 A값을 self.head로 바꿔 줘야합니다.

case 3#

현재 위치가 L에 있는 경우입니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def add(self, value): A = Node(value) Y = self.current X = Y.prev Z = Y.next # case 1, 2 A.prev = X A.next = Y if Y is not self.head: X.next = A else: self.head = A Y.prev = A self.current = A # 3 # X -> L (Y) # ^ # X -> A -> L # ^

케이스를 따져보니 기존에 만든 코드로 충분히 구현이 가능합니다.

case 4#

노드가 아직 생성되지 않을때입니다.

class Node: def \_\_init\_\_(self, data): self.data = data self.next = None self.prev = Noneclass LinkedList: def \_\_init\_\_(self): self.LAST = Node(None) self.current = self.LAST self.head = self.LAST def add(self, value): A = Node(value) Y = self.current X = Y.prev Z = Y.next # case 1, 2 , 3 A.prev = X A.next = Y if Y is not self.head: X.next = A else: self.head = A Y.prev = A self.current = A # 4 # L (Y) # ^ # A -> L # ^

이경우 역시 기존의 코드로 구현이 가능합니다.

이렇게 경우의수를 따져가면서 링크드 리스트를 구현하면 훨씬 구현하기가 쉽습니다. 코드를 깔끔하게 작성하고자 한다면 X, Y, Z로 치환된값을 모두 제거해주면됩니다!

다음글에는 이전위치 self.prev와 None으로 고정된 마지막 값 self.LAST를 없애는 방법에 대해 다뤄보겠습니다!