[링크드 리스트]
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
python으로 알고리즘 문제를 풀던 중에 링크드 리스트의 구현이 필요해져서 공부한 기록
일반적인 링크드 리스트의 노드는 아래와 같이 구현한다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
data는 현재 데이터, next는 다음 데이터를 가지고 있다.
이제 LinkedList를 구성해야 한다.
class LinkedList:
def __init__(self, data):
self.head = Node(data)
# 헤더부터 탐색하기
def append(self, data):
current = self.head
while current.next is not None:
current = current.next
current.next = Node(data)
# 마지막 노드로 이동
LinkedList를 처음 초기화 할 때 그 데이터로 만들어진 노드가 리스트의 헤더가 된다.
헤더부터 탐색해서 마지막 노드로 이동하는 append 함수를 만들어 준다. (나중에 사용)
노드를 추가 하거나 삭제하려면 index로 해당 노드의 값을 얻는 코드가 필요하다.
# 인덱스로 노드 값 얻기
def get_node(self,index):
cnt = 0
node = self.head
while cnt<index:
cnt+=1
node=node.next
return node
while문을 돌면서 현재 인덱스에 cnt=0 부터 index에 해당하는 값까지 이동한 후 node를 반환한다.
이제 삽입과 삭제 함수만 있으면 링크드 리스트를 사용할 수 있다.
# 삽입
def add_node(slef,index,value):
new_node = Node(value)
# 맨 위에 삽입
if index ==0:
new_node.next = self.head
self.head = new_node
return
node = self.get_node(index-1) #들어갈 자리의 이전 노드
next_node = node.next #이전 노드의 다음을 저장
node.next = new_node #이전 노드의 다음으로 삽입
new_node.next = next_node #삽입된 노드의 다음으로 이전 노드의 다음 저장
# 삭제
def del_node(self,index):
if index==0:
self.head = self.head.next
return
node = self.get_node(index-1)
node.next = node.next.next
#삭제 이전의 노드는 다다음 노드를 선택
코드에 주석을 달면서 내용을 이해했다.
<add_node>
add_node에서는 삽입을 담당하며 index를 통해서 이전 노드를 얻은 후에
이전 노드의 다음 노드로 새로운 노드를 추가, 새로 추가된 노드의 다음 노드로 이전 노드의 다음노드로 설정해준다.
만약에 [2] - [3] - [4] 의 1번 인덱스인 [3]에 데이터 [5]를 추가 하는 경우
1. [2]의 노드를 얻어온 후 [2]의 다음 노드에 [5]를 연결 [2].next = [5]
2. 새로 추가 된 [5]의 다음 노드에 기존 [2]의 다음 노드인 [3]을 연결 [5].next = [3]
결과로 [2]-[5]-[3]-[4] 를 얻을 수 있다.
<del_node>
del_node에서는 삭제를 담당하며 index를 통해서 이전 노드를 얻은 후에
이전 노드의 다음노드를 다다음 노드로 연결한다.
만약에 [2] - [3] - [4] 의 1번 인덱스인 [3]을 삭제하는 경우
1. [3]의 이전 노드인 [2]를 얻어온다.
2. [2]의 다음 노드를 [2]의 다다음 노드로 설정한다.
결과로 [2] - [4]를 얻을 수 있으며 [3]은 자동으로 삭제된다.
추가 함수보다 더 쉽게 삭제 함수를 구현할 수 있다.
다음에는 이중 연결 리스트를 공부해야겠다.