Linked List

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)