연결 리스트(Linked List)

연결 리스트(Linked List)

1. 개념

연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 선형 자료구조입니다. 각 노드는 메모리 상에서 연속적으로 저장되지 않고, 포인터를 통해 다음 노드와 연결됩니다.

2. 연결 리스트의 특징

• 동적 크기: 실행 시간에 크기를 조절할 수 있습니다.
• 삽입/삭제 효율성: 특정 위치에서의 삽입과 삭제가 O(1) 시간 복잡도로 수행됩니다.
• 임의 접근 비효율성: 특정 위치의 요소에 접근하기 위해 O(n) 시간이 필요합니다.
• 메모리 사용: 각 노드마다 데이터와 포인터를 저장하므로 배열보다 더 많은 메모리를 사용합니다.

3. 연결 리스트의 종류

3.1. 단일 연결 리스트(Singly Linked List)

각 노드가 데이터와 다음 노드를 가리키는 포인터를 가집니다.

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

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

3.2. 이중 연결 리스트(Doubly Linked List)

각 노드가 데이터와 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터를 가집니다.

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

3.3. 원형 연결 리스트(Circular Linked List)

마지막 노드가 첫 번째 노드를 가리키는 연결 리스트입니다. 단일 또는 이중 연결 리스트로 구현될 수 있습니다.

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

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

4. 기본 연산

4.1. 단일 연결 리스트 구현

노드 추가

def append(self, data):
    new_node = Node(data)
    
    # 리스트가 비어있는 경우
    if self.head is None:
        self.head = new_node
        return
    
    # 마지막 노드를 찾아 새 노드 추가
    last = self.head
    while last.next:
        last = last.next
    last.next = new_node

노드 삽입

def insert_after(self, prev_node, data):
    if prev_node is None:
        print("이전 노드가 연결 리스트에 존재하지 않습니다.")
        return
    
    new_node = Node(data)
    new_node.next = prev_node.next
    prev_node.next = new_node

노드 삭제

def delete_node(self, key):
    # 삭제할 노드 검색
    temp = self.head
    
    # 헤드 노드를 삭제하는 경우
    if temp and temp.data == key:
        self.head = temp.next
        temp = None
        return
    
    # 삭제할 노드 찾기
    while temp:
        if temp.data == key:
            break
        prev = temp
        temp = temp.next
    
    # 노드를 찾지 못한 경우
    if temp is None:
        return
    
    # 노드 연결 끊기
    prev.next = temp.next
    temp = None

연결 리스트 순회

def print_list(self):
    temp = self.head
    while temp:
        print(temp.data, end=" -> ")
        temp = temp.next
    print("None")

연결 리스트 길이 계산

def get_length(self):
    count = 0
    temp = self.head
    while temp:
        count += 1
        temp = temp.next
    return count

 

4.2. 이중 연결 리스트 구현

노드 추가

def append(self, data):
    new_node = Node(data)
    
    # 리스트가 비어있는 경우
    if self.head is None:
        self.head = new_node
        self.tail = new_node
        return
    
    # 마지막에 새 노드 추가
    new_node.prev = self.tail
    self.tail.next = new_node
    self.tail = new_node

노드 삽입

def insert_after(self, prev_node, data):
    if prev_node is None:
        print("이전 노드가 연결 리스트에 존재하지 않습니다.")
        return
    
    new_node = Node(data)
    
    # 마지막 노드 이후에 삽입하는 경우
    if prev_node == self.tail:
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node
        return
    
    # 중간에 삽입하는 경우
    new_node.next = prev_node.next
    new_node.prev = prev_node
    prev_node.next.prev = new_node
    prev_node.next = new_node

노드 삭제

def delete_node(self, node):
    # 노드가 헤드인 경우
    if node == self.head:
        self.head = node.next
        if self.head:
            self.head.prev = None
        # 리스트에 노드가 하나밖에 없는 경우
        if node == self.tail:
            self.tail = None
        return
    
    # 노드가 테일인 경우
    if node == self.tail:
        self.tail = node.prev
        self.tail.next = None
        return
    
    # 중간 노드를 삭제하는 경우
    node.prev.next = node.next
    node.next.prev = node.prev

양방향 순회

def print_forward(self):
    temp = self.head
    while temp:
        print(temp.data, end=" <-> ")
        temp = temp.next
    print("None")

def print_backward(self):
    temp = self.tail
    while temp:
        print(temp.data, end=" <-> ")
        temp = temp.prev
    print("None")

 

5. 연결 리스트의 시간 복잡도

연산 단일 연결 리스트 이중 연결 리스트 배열

접근	O(n)	O(n)	O(1)
검색	O(n)	O(n)	O(n)
삽입(처음)	O(1)	O(1)	O(n)
삽입(중간)	O(n)	O(n)	O(n)
삽입(끝)	O(n)	O(1)	O(1)*
삭제(처음)	O(1)	O(1)	O(n)
삭제(중간)	O(n)	O(n)	O(n)
삭제(끝)	O(n)	O(1)	O(1)

*파이썬의 동적 배열(리스트)에서는 일반적으로 O(1)이지만, 재할당이 필요한 경우 O(n)

 

6. 연결 리스트 활용 예제

6.1. 연결 리스트 뒤집기

def reverse(self):
    prev = None
    current = self.head
    
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    
    self.head = prev

6.2. 순환 감지(Floyd's Cycle-Finding Algorithm)

def detect_cycle(self):
    slow = self.head
    fast = self.head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

6.3. 중간 노드 찾기

def find_middle(self):
    slow = self.head
    fast = self.head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    return slow

6.4. 두 정렬된 리스트 병합

def merge_sorted_lists(list1, list2):
    dummy = Node(0)
    tail = dummy
    
    while list1 and list2:
        if list1.data <= list2.data:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    
    tail.next = list1 if list1 else list2
    
    return dummy.next

7. 연결 리스트 응용

7.1. LRU 캐시 구현

LRU(Least Recently Used) 캐시는 가장 오랫동안 사용되지 않은 항목을 제거하는 캐싱 전략입니다. 이중 연결 리스트와 해시 테이블을 조합하여 구현할 수 있습니다.

class LRUCache:
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        
        # 더미 노드 생성
        self.head = self.Node(0, 0)
        self.tail = self.Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_node(self, node):
        # 항상 헤드 다음에 새 노드 추가
        node.prev = self.head
        node.next = self.head.next
        
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        # 노드 제거
        prev = node.prev
        next = node.next
        
        prev.next = next
        next.prev = prev
    
    def _move_to_head(self, node):
        # 노드를 제거하고 헤드로 이동
        self._remove_node(node)
        self._add_node(node)
    
    def _pop_tail(self):
        # 테일 바로 앞의 노드 제거 및 반환
        res = self.tail.prev
        self._remove_node(res)
        return res
    
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._move_to_head(node)
            return node.value
        return -1
    
    def put(self, key, value):
        if key in self.cache:
            # 키가 이미 존재하면 값 업데이트 및 헤드로 이동
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            # 새 노드 생성 및 추가
            node = self.Node(key, value)
            self.cache[key] = node
            self._add_node(node)
            
            # 용량 초과 시 가장 오래된 항목(테일) 제거
            if len(self.cache) > self.capacity:
                tail = self._pop_tail()
                del self.cache[tail.key]

7.2. 다항식 표현

연결 리스트를 사용하여 다항식을 표현하고 연산할 수 있습니다.

class PolynomialNode:
    def __init__(self, coefficient, exponent):
        self.coefficient = coefficient
        self.exponent = exponent
        self.next = None

class Polynomial:
    def __init__(self):
        self.head = None
    
    def append(self, coefficient, exponent):
        new_node = PolynomialNode(coefficient, exponent)
        
        if self.head is None:
            self.head = new_node
            return
        
        # 지수에 따라 정렬된 상태 유지
        if exponent > self.head.exponent:
            new_node.next = self.head
            self.head = new_node
            return
        
        temp = self.head
        while temp.next and temp.next.exponent >= exponent:
            temp = temp.next
        
        new_node.next = temp.next
        temp.next = new_node
    
    def add(self, other):
        result = Polynomial()
        p1 = self.head
        p2 = other.head
        
        while p1 or p2:
            if p1 is None:
                result.append(p2.coefficient, p2.exponent)
                p2 = p2.next
            elif p2 is None:
                result.append(p1.coefficient, p1.exponent)
                p1 = p1.next
            elif p1.exponent == p2.exponent:
                sum_coef = p1.coefficient + p2.coefficient
                if sum_coef != 0:
                    result.append(sum_coef, p1.exponent)
                p1 = p1.next
                p2 = p2.next
            elif p1.exponent > p2.exponent:
                result.append(p1.coefficient, p1.exponent)
                p1 = p1.next
            else:
                result.append(p2.coefficient, p2.exponent)
                p2 = p2.next
        
        return result
    
    def print_polynomial(self):
        if self.head is None:
            print("0")
            return
        
        temp = self.head
        terms = []
        
        while temp:
            if temp.coefficient != 0:
                term = ""
                if temp.coefficient != 1 or temp.exponent == 0:
                    term += str(temp.coefficient)
                
                if temp.exponent > 0:
                    if temp.coefficient != 1:
                        term += "x"
                    else:
                        term += "x"
                    
                    if temp.exponent > 1:
                        term += "^" + str(temp.exponent)
                
                terms.append(term)
            
            temp = temp.next
        
        print(" + ".join(terms) if terms else "0")

9.2. k번째 마지막 노드 찾기

def find_kth_from_end(head, k):
    if not head or k < 1:
        return None
    
    # 두 포인터 사용: 하나는 k만큼 앞서서 이동
    ahead = head
    behind = head
    
    # ahead 포인터를 k만큼 앞으로 이동
    for _ in range(k):
        if not ahead:
            return None  # 리스트가 k보다 짧음
        ahead = ahead.next
    
    # 두 포인터를 함께 이동, ahead가 끝에 도달하면 behind는 k번째 마지막 노드
    while ahead:
        ahead = ahead.next
        behind = behind.next
    
    return behind

8. 연결 리스트의 장단점

8.1. 장점

- 동적 크기 조정: 미리 크기를 지정할 필요가 없고 실행 시간에 크기가 조정됩니다.
- 삽입/삭제 효율성: 특정 위치(포인터가 있는 경우)에서의 삽입과 삭제가 O(1) 시간 복잡도로 매우 효율적입니다.
 - 메모리 활용: 필요한 만큼만 메모리를 사용하므로 메모리 낭비가 적습니다.
 - 구현 용이성: 다양한 자료구조(스택, 큐, 그래프 등)의 기본 구성 요소로 사용됩니다.

8.2. 단점

- 임의 접근 비효율성: 특정 인덱스의 요소에 접근하려면 처음부터 순차적으로 탐색해야 합니다(O(n) 시간 복잡도).
- 추가 메모리 사용: 각 노드마다 데이터 외에도 포인터를 저장해야 하므로 배열보다 메모리 오버헤드가 큽니다.
- 캐시 지역성 부족: 메모리상에서 연속적으로 저장되지 않아 캐시 효율성이 떨어집니다.
- 역방향 탐색 어려움: 단일 연결 리스트에서는 이전 노드로 돌아가기 어렵습니다(이중 연결 리스트로 해결 가능).

 

9. 연결 리스트 관련 문제

9.1. 두 연결 리스트의 교차점 찾기

def get_intersection_node(head1, head2):
    if not head1 or not head2:
        return None
    
    # 각 리스트의 길이 계산
    len1 = get_length(head1)
    len2 = get_length(head2)
    
    # 길이 차이 계산
    diff = abs(len1 - len2)
    
    # 더 긴 리스트의 포인터를 diff만큼 먼저 이동
    if len1 > len2:
        longer, shorter = head1, head2
    else:
        longer, shorter = head2, head1
    
    for _ in range(diff):
        longer = longer.next
    
    # 두 포인터가 만날 때까지 함께 이동
    while longer and shorter:
        if longer == shorter:
            return longer
        longer = longer.next
        shorter = shorter.next
    
    return None

def get_length(head):
    length = 0
    while head:
        length += 1
        head = head.next
    return length

9.3. 회문(Palindrome) 연결 리스트 확인

def is_palindrome(head):
    if not head or not head.next:
        return True
    
    # 중간 노드 찾기
    slow = head
    fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # 후반부 뒤집기
    second_half = reverse_list(slow.next)
    
    # 앞반부와 뒤집은 후반부 비교
    first_half = head
    while second_half:
        if first_half.data != second_half.data:
            return False
        first_half = first_half.next
        second_half = second_half.next
    
    return True

def reverse_list(head):
    prev = None
    current = head
    
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    
    return prev

 

10. 연결 리스트 구현 최적화

10.1. 더미 노드(Dummy Node) 활용

더미 노드를 사용하면 특별한 경우(빈 리스트, 헤드 삽입 등)를 처리하는 코드를 단순화할 수 있습니다.

class LinkedList:
    def __init__(self):
        self.dummy = Node(None)  # 더미 노드
        self.size = 0
    
    def insert(self, index, data):
        if index < 0 or index > self.size:
            raise IndexError("Index out of range")
        
        current = self.dummy
        for _ in range(index):
            current = current.next
        
        new_node = Node(data)
        new_node.next = current.next
        current.next = new_node
        self.size += 1
    
    def remove(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        
        current = self.dummy
        for _ in range(index):
            current = current.next
        
        removed = current.next
        current.next = removed.next
        self.size -= 1
        return removed.data

10.2. 테일 포인터(Tail Pointer) 활용

마지막 노드를 가리키는 포인터를 유지하면 끝에 삽입하는 연산을 O(1) 시간에 수행할 수 있습니다.

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def append(self, data):
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
        else:
            self.tail.next = new_node
        
        self.tail = new_node
        self.size += 1

 

11. 결론

연결 리스트는 데이터를 순차적으로 저장하는 동적 자료구조로, 메모리의 효율적인 사용과 데이터의 삽입/삭제가 빈번한 상황에서 유용합니다. 그러나 임의 접근이 자주 필요한 경우에는 배열이나 다른 자료구조가 더 적합할 수 있습니다.

파이썬에서는 내장 리스트 자료형이 이미 동적 배열로 구현되어 있어 많은 경우에 충분히 효율적이지만, 특정 알고리즘 문제 해결이나 자료구조의 이해를 위해 연결 리스트의 개념과 구현 방법을 아는 것이 중요합니다.

모든 자료구조와 마찬가지로, 연결 리스트도 특정 상황에 맞는 장단점을 가지고 있으므로 문제 상황에 적합한 자료구조를 선택하는 것이 알고리즘 설계의 핵심입니다.