배열(Array)은 순차적으로 연결된 공간에 데이터를 나열하는 자료구조이고, 링크드 리스트(Linked List)는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 자료구조 입니다. 배열은 미리 특정한 연결된 공간을 확보하고 데이터를 쓰고 있는 자료구조이고, 링크드 리스트는 필요할 때 마다 데이터를 추가할 수 있는 구조입니다. 배열의 단점을 극복한 자료구조가 링크드 리스트라고 볼 수 있습니다.
출처: https://velog.io/@keemtj/자료구조-링크드-리스트Linked-List
Linked List는 노드라는 객체로 이루어져 있습니다.
위 그림과 같이 Data를 저장할 공간과 다음 주소를 가리킬 공간이 필요합니다. 사용자가 입력하는 정보를 DATA영역에 담고 노드가 추가될 때마다 Next address를 이용하여 다음 노드와 연결합니다.
전체적인 연결리스트 구조는 아래와 같이 나타낼 수 있습니다.
이와 같이 각 노드는 연속된 공간에 저장되어 있지 않고 메모리의 여러 부분에 분포되어 있습니다.
각 노드에 다음 노드의 주소를 저장함으로써 다음 노트를 탐색할 수 있습니다. 다음 주소를 가리켜야 하기 때문에 포인터를 이용해 구현할 수 있습니다.
노드가 가리키는 다음 주소가 NULL이면 이 노드는 마지막 노드라고 할 수 있습니다.
Linked List를 구현하기 위해서는 다음과 같은 함수를 구현해야 합니다.
초기화(init) / 삽입(Insert) / 삭제(Remove)
Init
노드를 생성하는 과정입니다.
노드를 접근하기 위해서는 맨 처음 노드의 주소를 가리킬 노드가 필요합니다. 이 노드를 head라고 표현하겠습니다.
또한 나중에 구현할 삽입의 시간복잡도를 줄이기 위해 마지막 노드를 가리키는 노드 tail을 하나 만들겠습니다.
초기화하는 과정에서 다음 주소를 가리키는 포인터는 null로 설정합니다. null은 '가리키는 노드가 없음' 을 의미합니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, data):
self.head = Node(data)
#헤더부터 탐색해 뒤에 새로운 노드 추가하기
def append(self, data):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(data)
#모든 노드 값 출력
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
cnt = 0
node = self.head
while cnt < index:
cnt += 1
node = node.next
return node
Insert
새로운 노드가 들어올때는 현재 노드의 next 를 new node로 바꿔주고 new node의 next를 원래 cur node의 next노드로 바꿔주면 됩니다.
즉 [3] → [4] → [1] → [2]를 [3] → [4] → [5] → [1] → [2] 만들기 위해서 인덱스 2자리인 [1]에 들어가기 위해 [4] 노드 위치를 파악하고, 그 다음 next에 [5] 노드를 연결해줍니다. [5]의 next는 [1]이 연결되게끔 해야합니다.
def add_node(self, 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