[딩코딩코 2025 코딩테스트 필수 알고리즘] - 5. LinkedList 구현

본 글에 사용된 코드와 이미지의 일부는
딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp\

---

이번 글에서는 앞서 알아본 LinkedList 를 구현해보려고 한다.

LinkedList 는 노드와 포인터 로 구성되어 있다.

즉, 칸에 있는 데이터, 다음 칸이 뭔지 두 가지 정보가 필요하다.

LinkedList 구현

두 가지 데이터를 가지고 있어야 하기 때문에 클래스 를 이용하면 된다.

1. Node 클래스

우선 클래스의 생성자에 data 를 인자로 받아서 self.data 에 저장한다. 그리고 다음 이어진 노드가 없기 때문에 self.next 에는 None 을 넣어두면 된다.

위 내용을 코드로 작성해보자.

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

# 3을 가진 Node 를 만듦
node = Node(3) # 현재 [3] , next 없음

2. Node 연결하기

위와 같이 Node 클래스를 만들었으니, 이제 노드들을 만들어서 연결을 해보자.

first_node = Node(5) # [5] 노드 
second_node = Node(12) # [12] 노드
first_node.next = second_node # [5] -> [12]

이렇게 작성하면 노드가 추가될 때 마다 반복해야 하는데 너무 번거롭다. 따라서 LinkedList 라는 클래스를 추가해 번거로움을 해결해보자.

3. LinkedList 클래스

LinkedList 는 head node 만 가지고 있다. 기차 예시를 떠올려보면, 맨 앞 칸만 저장해두고, 다음 칸을 보기 위해서는 next 를 통해 다음 노드에 접근해야 한다.

즉, LinkedList 는 self.head 에 시작하는 노드를 저장하고 , 다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다.

class LinkedList:
        def __init__(self,value):
                self.head = Node(value) # head 에 시작하는 Node 를 연결

linked_list = LinkedList(5)
print(linked_list.head.data) # 5가 출력

4. append 함수

다음으로는, LinkedList 의 맨 뒤에 새로운 Node 를 붙이는 append 함수를 만들어보자.

현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가해주면 된다. 그러기 위해서는 가장 맨 뒤의 노드까지 가야 한다.

맨 뒤의 노드까지 가려면 어떻게 해야 할까? 바로 , head 를 따라서 계속 이동하면 된다.

head 를 변경시킬 수는 없으니 , cur 이라는 변수를 이용해보자.

cur = this.head 에 넣으면 아래와 같이 되고,

cur
[3] → [5] → [6] → [8]

cur = cur.next 을 하면 다음과 같이 한 칸 이동한다.

      cur
[3] → [5] → [6] → [8]

위와 같은 방법을 맨 뒤의 노드까지 반복하면 된다. 맨 뒤의 노드는 cur.nex 가 None 이라는 것을 의미한다.

코드로 작성해보자.

class LinkedList:
        def __init__(self,value): 
                self.head = Node(value) # head 에 시작하는 Node 를 연결

        def append(self,value): # LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결
                cur = self.head
                while cur.next is not None: # cur의 다음이 끝에 갈 때까지 이동합니다. 
                        cur = cur.next
                cur.next = Node(value)

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

5. print_all 함수

위에서 append 함수를 작성했는데 제대로 값이 들어갔는지 확인하기 어렵다. 그래서 print_all 이라는 함수를 만들어 저장한 헤드를 따라가면 현재 있는 노드들을 전부 출력해보자.

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

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

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
                print(cur.data)
                cur = cur.next

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.print_all()

---

LinkedList 원소 찾기

“링크드 리스트에서 index 번째 원소를 반환하시오”

이 문제를 해결하기 위해서 어떻게 해야 될까?

1. 노드를 따라가면서 값을 찾는다.
2. head 에 저장되어 있는 노드를 cur 변수에 담는다.
3. count 라는 인덱스를 저장하기 위한 변수를 저장한다.
4. count 가 index 가 될 때 까지 node 의 next 값을 node 에 대입하고 count 를 증가한다.
5. 위 과정을 count 가 index 가 아닐때까지 반복한다.
6. node 를 반환한다.

위 과정을 코드로 작성해보자.

def get_node(self,index):
        cur = self.head
        cur_index = 0

        while cur_index != index:
                cur = cur.next
                cur_index += 1

        return cur

 

---

LinkedList 원소 추가

“링크드 리스트에서 index 번째 원소를 추가하시오”

****이 문제를 해결하기 위해서 어떻게 해야 될까?

1. 화물칸을 생각해보자.
   1. 자갈 칸의 연결 고리를 흑연 칸으로 연결한다. ["자갈"] -> ["흑연"] ["밀가루"] -> ["우편"]
   2. 흑연 칸의 연결고리를 밀가루 칸으로 연결한다. ["자갈"] -> ["흑연"] -> ["밀가루"] -> ["우편"]
   3. 이 때, 밀가루 칸의 위치를 저장해둬야 흑연 칸을 밀가루 칸에 연결할 수 있다.
2. next_node 라는 변수에 현재 노드와 연결된 노드를 저장한다.
3. 현재 노드의 다음 노드를 새로운 노드와 연결한다.
4. 새로운 노드의 다음 노드를 이전에 저장해둔 노드에 연결한다.

위 과정을 코드로 작성해보자.

def add_node(self,index,value):
        new_node = Node(value)
        node = self.get_node(index -1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

그런데 여기서 주의 할 점이 있다.

index - 1 이 -1 이 되는 경우에 어떻게 해야 될까? 만약 0 이 입력된다면 get_node(-1) 이 호출되어서 원하지 않는 동작이 나온다.

따라서, 이런 경우에는 예외처리를 따로 해줘야 한다. 새로운 노드의 next 를 현재 가지고 있는 head 에 연결하고, 우선 현재 가지고 있는 head 를 새로운 노드로 교체해주면 된다.

def add_node(self,index,value):
        new_node = Node(value)
        if index == 0:
                new_node.next = self.head
                self.head = new_node
                return

        prev_node = self.get_node(index -1)
        next_node = prev_node.next
        prev_node.next = new_node
        new_node.next = next_node

---

LinkedList 원소 삭제

“링크드 리스트에서 index 번째 원소를 제거하시오”

****이 문제를 해결하기 위해서 어떻게 해야 될까?

1. 화물칸을 생각해보자.
   1. 흑연 칸의 연결고리를 떼어낸다.
      ["자갈"] → ["흑연"] ["밀가루"] → ["우편"]
   2. 우편 칸으로 연결한다.
   3. ["자갈"] -> ["흑연"] -> ["우편"] ["밀가루"]
   4. 흑연 칸의 포인터를 다음 다음 칸으로 연결하면 된다.

위 과정을 코드로 작성해보자.

def delete_node(self,index):
        node = self.get_node(index-1)
        node.next = node.next.next

여기서도 원소 추가에서 와 똑같이 index-1 에서 주의해야 한다.

만약 0번째의 노드를 제거하고 싶다면, 현재 head 의 다음 노드를 head로 만들면 된다.

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