🔥 TIL - Day 33

📌 LinkedList ?

노드와 포인터로 이뤄진 자료구조로 Array와 같이 일련의 데이터를 담을 수 있는 자료구조이다.

Array랑 무엇이 다른가?

• Array에 비해 삽입, 삭제 등 수정에 용이하다.
  LinkedList에서 수정은 단지 연결을 끊고 또 연결하는 것이다.
  Array는 삽입, 삭제시 최악의 경우 Array의 크기만큼의 연산횟수를 갖는다 (= O(N))

• but, Array에 비해 조회성능이 떨어진다.
  조회하고자 하는 노드가 가장 끝에 있다면 O(N)의 시간복잡도를 갖는다. 포인터를 타고 올라가며 쭈~욱 순회해야 함!

• 조회가 자주 발생한다면 ? Array 👍

• 수정이 자주 발생한다면 ? LinkedList 👍

---

📌 LinkedList 직접 구현

LinkedList는 값을 담는 node와 다음 node를 가리킬 pointer가 있어야 한다. 이런 구조는 아래와 같이 구현 가능하다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

이제 Node 클래스를 이용해서 LinkedList를 구현한다.
List의 주요 연산인 조회, 삽입, 삭제를 구현한다.

LinkedList는 반드시 반드시 반드시 Head 노드를 가져야 한다. 그러니 LinkedList의 생성자에서 무조건 Head 노드가 생성되도록 한다.

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

...

# 생성
linked_list = LinkedList(1)

LinkedList를 조작하는 것에 있어서 뽀인트는 LinkedList 순회시 head 노드를 직접 움직이지 않고 복사해서 사용해야 한다는 것이다. (head는 움직이면 안됨!)

cur = self.head

조회 (n번째 노드 조회)

index 까지 next를 반복하며 포인터를 옮기고 index번 째에 도달했을 때 루프를 나와서 해당 노드를 반환한다.

def get(self, index):
    cur = self.head
    cnt = 0
    while cnt < index:
        cur = cur.next
        cnt += 1
    return cur

삽입 (가장 뒤에 삽입 append)

head 노드부터 next를 이용해서 다음 노드로 이동하면서 다음 노드를 가리키지 않을 때까지 이동한다 (next)

다음 노드가 None이라면 While 문을 탈출하고 해당 node의 next로 노드를 생성한다.

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)

삽입 (중간에 삽입 insert)

n번째에 삽입하고 싶다면 n-1번째 노드의 next가 삽입하고자 하는 노드를 가리키고 원래 삽입되는 노드는 원래 n번째 노드를 가리키도록 하면 된다.

중요한 것은 원래의 n-1 번째 노드와 n번째 노드의 연결을 끊기 이전에 n번째 노드를 반드시 저장해둬야 한다. 아니면 다시 참조할 수 없다.

[ 이부분 !! ]
next_node = curr_node.next

def insert(self, index, value):
    if index == 0:
        next_node = self.head
        self.head = Node(value)
        self.head.next = next_node
        return
    # -1 번째를 찾는다면 언제나 0일 때 예외상황을 생갹해야 한다.
    curr_node = self.get(index - 1)
    new_node = Node(value)
    next_node = curr_node.next
    curr_node.next = new_node
    new_node.next = next_node

삭제

제일 간단하다 👍

def delete(self, index):
    if index == 0:
        self.head = self.head.next
        return
    prev_node = self.get(index - 1)
    prev_node.next = prev_node.next.next

알고리즘 주간 Start !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!