https://davinci-ai.tistory.com/16 를 참고하여 쓴 글임을 미리 알립니다.
연결리스트 라고도 불리는 링크드 리스트는 배열과 달리 연결되지 않고, 떨어진 곳에 존재하는 데이터를 경로로 지정하여 관리하는 데이터 구조이다.
파이썬에서는 리스트 자료구조가 링크드 리스트 기능을 모두 지원한다.
기능
Node : 데이터 저장 단위로, 데이터 값 + 포인터로 구성
Pointer : 각 노드 안에서, 다음이나 이전의 노드 주소를 가지는 값을 의미
장점:
미리 데이터 공간을 할당할 필요가 없다.
중간에 데이터 삽입 및 삭제를 하는데 리스트보다 효율이 좋다.
n개의 원소가 있는 연결리스트를 한번 순회를 하면서 중간 중간 데이터를 m개를 삽입을 해야한다면
배열은 시간 복잡도가 O(mn)
연결리스트는 시간 복잡도가 O(m + n)
단점:
연결을 위한 별도 데이터 공간이 필요하므로 효율이 낮다.
데이터를 찾는데 접근성이 안 좋아서 속도가 느리다.
중간 데이터 삭제시 앞 뒤를 모두 고려하여 재구성하는 코드를 작성해야 한다.
파이썬으로 Node의 구현
class Node
def __init__(self,data):
self.data = data
self.next = None노드는 data를 저장하는 변수와 다음 노드를 가리키는 포인터가 있다.
해당 코드에서는 next라는 변수로 두었다.
파이썬으로 Linked List의 구현
Tip.
del문은 Python에서 변수를 삭제하는데 사용된다. 프로그램에 더이상 필요하지 않은 큰 목록이나 배열 등과 같은 변수를 삭제할 수 있다.
변수를 삭제한 후 사용하거나 엑세스하려고 하면 엑세스하려는 변수가 변수 네임 스페이스에 더 이상 존재하지 않기 때문에 NameError 예외를 리턴한다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
node = self.head
while node.next:
node = node.next
node.next = new_node
def delete(self, data):
node = self.head # 이 때 node는 헤드
if node.data == data: # 헤드의 데이터가 삭제할 데이터일 때
self.head = node.next
del node
# del은 변수는 그냥 삭제, iterable객체내의 성분은 그 성분만 삭제한다.
else:
while node.next: #node의 next가 None이면 자동으로 반복 종료
next_node = node.next
if next_node.data == data:
node.next = next_node.next
del next_node
else:
node =node.next
def find(self, data):
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
def print(self):
node = self.head
while node:
print(node.data)
node = node.next링크드 리스트에서는 head인 첫번째 노드의 정보만 알면 된다.
그리고 데이터를 받아서 Node를 만들어 리스트에 추가시켜줄 add함수, node의 data값을 통해 리스트에서 제거하는 delete함수, data값으로 Node를 찾아주는 find함수, 현재 링크드 리스트의 모든 노드의 데이터값을 출력하는 print함수를 간단하게 구현하였다.
