Linked List

Linked List는 Array와 겉보기에 비슷한 구조를 가지고 있다.

하지만 Array와 Linked List는 확연하게 다르다.

Array vs Linked List

Array

일반적인 배열을 뜻한다. 접근이 쉽지만 삽입이 어렵다.

삽입이 어렵다는 말은 [1,2,3,4,5] 리스트가 있고, 3 뒤에 새로운 숫자를 넣고 싶다면 [4,5]를 제거한 뒤 새로운 숫자를 넣고 다시 [4,5]를 넣어줘야 하는 번거로움이 존재한다.

또한 모든 공간이 차버리게 되면 새로운 메모리 공간을 할당해야 한다.

Linked List

배열과 유사하지만 각 Node가 존재하고, 각 노드는 다음 노드에 대한 정보를 가지고 있다.

즉, Linked List에 새로운 값을 넣거나 빼고 싶다면 부품을 갈아 끼우듯이 원하는 위치에 값을 넣었다 뺐다 하기 쉽다. 또한 정해진 공간에서 값을 추가하는게 아닌 Node를 연결하는 것이기 때문에 동적이다.

하지만 Linked List 직접 구현해야 하는 번거로움이 있고, 값에 접근하기가 까다롭다.

✅ 정리

데이터에 접근하는 경우가 빈번하다면 Array를 사용하고, 삽입과 삭제가 빈번하다면 Linked List를 사용하는 것이 좋다.

---

Linked List 구현 코드

📃 code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        if not self.head:
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next

        node.next = ListNode(val, None)

1. Linked List는 Node로 이루어져 있다. 해당 Node에는 값과 다음 Node에 대한 값이 들어있다.

2. Linked List에 새로운 값을 추가 하는 방법은 Node의 next 필드에 새로운 값을 추가하면 된다.

3. 중간에 값을 추가하거나 삭제하고 싶은 경우

추가

값을 추가하고 싶은 위치의 바로 앞 Node를 찾아서 next(다음 노드)에 해당 Node를 넣고, 새로운 Node의 next에 기존의 next Node를 추가 하면 된다.

삭제

값을 삭제하고 싶은 위치의 바로 앞 Node를 찾아서 next(다음 노드)에 삭제할 노드의 next에 있던 Node를 저장하면 된다.

---

🤔 Linked List를 굳이 번거롭게 써야 하나...?

Linked List의 경우 구현의 번거로움이 있지만 메모리 관리, 삽입 및 삭제의 경우 배열보다 좋은 성능을 가질 수 있기 때문에 상황에 따라서 Array보다 효율적일 수 있다.