02 - Array & Linked List

https://www.faceprep.in/data-structures/linked-list-vs-array/ 출처

 

링크드리스트(Linked List)는 데이터(노드)들이 포인터(참조)로 서로 연결된 자료구조입니다.

배열처럼 “칸”이 연속으로 붙어있는 게 아니라,

필요할 때 노드를 만들어 연결하는 방식이라서 삽입/삭제에 강한 편 입니다.

 

링크드리스트를 활용한 문제풀이

 

1) 구성요소

• Node(노드): 보통 값(value) + 다음(next)(필요하면 이전(prev)도) 로 구성
• Head(헤드): 첫 노드를 가리킴
• (옵션) Tail(테일): 마지막 노드를 가리킴

2) 종류

• 단일 연결 리스트(Singly): next만 있음
  A → B → C → null
• 이중 연결 리스트(Doubly): prev, next 둘 다 있음
  null ← A ↔ B ↔ C → null
• 원형 연결 리스트(Circular): 마지막이 다시 처음을 가리킴
  A → B → C → A ...

3) 시간복잡도(핵심만)

• 맨 앞 삽입/삭제: O(1)
• 특정 위치 삽입/삭제: 그 위치를 찾는 데 O(n) + 연결 바꾸는 건 O(1)
• 탐색(검색): O(n) (배열처럼 인덱스로 바로 못 감)
• 인덱스 접근: O(n)

4) 장단점

장점

• 중간에 끼워넣기/삭제가 비교적 쉬움(연결만 바꾸면 됨)
• 크기 가변(필요한 만큼만)

단점

• 접근/검색이 느림(O(n))
• 포인터 저장 공간이 추가로 듦
• 캐시 친화성이 떨어져 배열보다 느릴 때가 많음

5) 언제 쓸까

• 삽입/삭제가 잦고, 데이터 크기가 자주 변하는 경우
• 스택/큐 같은 구조를 링크드리스트로 구현할 때(특히 head 기준)

 

링크드 리스트를 활용한 문제를 풀어봤다

 

Linked List - append 함수 만들기

# ["시멘트"]

class Node:

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

node = Node(3)
print(node.data, node.next)

next_node = Node(3)
node.next = next_node


class LinkedList:

    def __init__(self, value):
        self.head = Node(value)
#       LinkedList 의 가장 끝에 있는 노드에 새로운 노드를 연결해줘

    def append(self, value):
        cur = self.head

        while cur.next is not None:
            cur = cur.next

        cur.next = Node(value)
#       Linked_list 에서 저장한 head 를 따라가면서 현재 있는 노드들을 전부 출력해주는 함수.
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next


linked_list = LinkedList(5)
print(linked_list.head.data)

linked_list.append(12)
# 5 -> 12
linked_list.append(8)
# 5 -> 12 -> 8

linked_list.print_all()

 

Linked list - 원소찾기

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

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

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

        return cur
    
        return "index 번째 노드를 반환해보세요!"

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


print(linked_list.get_node(1).data) # -> 5를 들고 있는 노드를 반환해야 합니다!

 

두 링크드 리스트의 합 계산

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 get_single_linked_list_sum(linked_list):
    sum = 0
    cur = linked_list.head
    while cur is not None:
        sum = sum * 10 + cur.data
        cur = cur.next

    return sum


def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = get_single_linked_list_sum(linked_list_1)
    sum_2 = get_single_linked_list_sum(linked_list_2)

    # 구현해보세요!
    return sum_1 + sum_2


linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)
# head를 가지고 시작한다.
# cur
# sum_1 = 6

#        cur
# sum_1 = 6 * 10 + 7 = 67

#                 cur
# sum_1 = 67 * 10 + 8 = 678 이렇게 노드 이동
# [6] -> [7] -> [8] linked_list 의 1을 구하는게 중요하다 이걸 어떻게 구할것이냐

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
# [3] -> [5] -> [4]
print(get_linked_list_sum(linked_list_1, linked_list_2))