Linked List
2023. 2. 19. 16:40ㆍ알고리즘
반응형
Linked List
-Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조
-각 Node에는 데이터와 다음 노드의 주소값이 들어가있다.
-메모리에는 각 Node가 비연속적으로 저장되어 있지만 각 노드에는 다음 노드의 메모리 주소를 알기에 논리적으로는 연속성을 갖고있다.(물리적으로 비연속, 논리적으로 연)
-메모리가 연속적으로 있지 않으니 메모리 사용에는 자유로우나 각 노드당 데이터뿐만 아니라 다음 노드의 메모리 주소를 저장해야 하니 데이터 하나당 차지하는 메모리가 더 커진다.
VSCode에서 Linked List를 구현해보자
#Node는 Linked List에서 각 데이터와 다음 Node를 가리키는 데이터가 들어있는 객체이다
#Node가 연결되어서 하나의 Linked List가 되는거다.
class Node:
#생성자
def _init_(self, value = 0, next = None):
self.value = value
self.next = next
#노드 생성시 그 노드의 값(value)과 다음 노드(next)의 값을 넣어준다.
#세개의 노드를 만들었고 각각 value를 가지고 있다.
first = Node(1)
second = Node(2)
third = Node(3)
#각 노드에 다음 Node를 가리키도록 데이터를 넣어준다.
first.next = second
second.next = third
#위에 만들어진 Node를 통해서 Linked List를 구현해보자
class LinkeList :
#생성자
def _init_(self):
self.head = None
#head는 맨처음 생기는 Node 가 들어갈거다.
#Linked List에 노드 추가하기
def append(slef, value):
new_node = Node(value)
if self.new_node is None:#처음으로 Node를 추가할 경우 head에 추가하는 노드가 들어간다.
self.head = new_node
else:# 처음으로 추가하는것이 아닌 경우
current = self.head#맨 처음에 들어간 노드
while(current.next):#맨 처음들어간 노드부터 시작해서 next 값이 없는 노드가 나올때까지 반복 loop
current = current.next#head부터 계속 다음노드로 간다.
#다음 노드가 없어서 while문을 빠져 나왔으면 다음 노드가 없는 노드의 next에 새로 추가한 node를 넣어준다.
current.next = new_node
li = LinkeList()
li.append(2)
li.append(4)
li.append(6)
li.append(8)
반응형