Linked List(링크드 리스트, 연결리스트) - 파이썬(Python)

Linked List(링크드 리스트, 연결리스트)🚂

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

참조: https://en.wikipedia.org/wiki/Linked_list

(발번역중🥲) 컴퓨터 공학에서, 링크드 리스트는 데이터 요소들의 선형적 집합이고, 그 순서는 메모리 배치에 따라 정해지는 것이 아니다. 대신에 각 요소는 다음 요소를 가리키고 있다. 이것은 순차적으로 표현 된 노드들 집합으로 이루어진 자료 구조다.

• 화물 열차를 생각하면 쉽다

  [짐칸1] - [짐칸2] - [짐칸3] - ...

• 중간에 삽입/추가를 앞 뒤 포인터만 변경하면 된다. (가리키는 포인터를 잘 지정)

  (추가)
  [짐칸1]             [짐칸2] - [짐칸3] - ...
        ↘️ [승객칸1] ↗️
  
  (삭제)
  [짐칸1] -----> [짐칸3]
         [짐칸2]
           ⬇️

• 특정 원소 탐색 시, 처음 부터 끝까지 탐색할 수 있다. 시간복잡도 O(n)

• Python의 list는 배열로 구현 but 동적으로 원소 추가 가능 (Array, Linkedlist 짬뽕)

• 클래스를 이용하여 Linked List를 구성하면 아래와 같다.

  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):
           if self.head is None:
               self.head = Node(data)
               return
  
           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):
           node = self.head
           count = 0
           while count < index:
               node = node.next
               count += 1
           return node
  
       # 특정 인덱스에 노드 추가
       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
  
       # 특정 인덱스 노드 삭제
       def delete_node(self, index):
           if index == 0:
               self.head = self.head.next
               return
           node = self.get_node(index-1)
           node.next = node.next.next
  

• 이제야 이해가 된 링크드 리스트!! 제발 내 머릿속에서 떠나지 말고 평생 있어줘~