연결 리스트(Linked List)

연결리스트란?

데이터를 저장할 때 각 요소가 다음 요소의 주소(또는 포인터)를 함께 저장하는 선형 자료구조이다. 배열과 달리 연속되지 않은 위치에 저장되며, 노드라고 불리는 단위(Node)로 구성됨. 즉, 노드(Node) 안에는 data와 포인터(next)가 있고, 이러한 노드들의 집합이다.

 

연결리스트(Linked List)   vs 배열(Array)

	연결 리스트	배열
메모리 구조	비연속적으로 할당(노드 단위)	연속적으로 할당(한 번에 확보)
메모리 할당 방식	필요한 만큼 한 개씩 동적 할당	전체 크기를 미리 정하고 고정 할당
삽입/삭제 효율성	노드 연결만 바꾸면 되어 효율적	요소 이동이 필요함 -> 비효율적
접근 방식	순차 접근만 가능(임의 접근 불가O(n))	인덱스를 이용해 임의 접근 가능(O(1))
공간 활용	메모리 낭비 적음(필요할 때만 할당)	낭비 가능성 있음(남는 공간 포함)

 

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List) : 노드가 다음 노드만을 가리킴.

2. 이중 연결 리스트(Doubly Linked List) : 노드가 전 노드와 다음 노드 모두를 가리킴.

3. 순환 연결 리스트(Circular Linked List) : 마지막 노드가 다시 처음 노드를 가리킴.

 

장점

리스트 처음, 끝,중간 모두 삽입, 삭제의 속도가 굉장히 빠르다. (O(1)) 

메모리를 효율적으로 사용 가능하다.

 

단점

요쇼를 찾는데 속도가 느림(O(n))

오버헤드가 큼

메모리가 연속적이지 않아 캐쉬 비효율

 

언제 사용하면 좋을 까?

중간에 삽입,삭제가 많을 때 사용하는 것이 좋음.

 

단일 연결 리스트 구현(with Python) 

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

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

    def insert(self, node_): # 삽입(끝에만)
        if self.head is None:
            self.head = node_
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node_

    def delete(self, node_): #삭제
        cur = self.head
        prev = None
        while cur != node_:
            prev = cur
            cur = cur.next
            if cur is None:
                return False

        if prev is None: # case 1:삭제하고자 하는 노드가 head일 경우
            self.head = cur.next
            return True

        if cur.next is None: # case 2: 꼬리일 때
            prev.next = None
            return True

        else: # case 3: 중간 노드일 때
            prev.next = cur.next
            return True

    def search(self, data):
        cur = self.head
        while (cur.data != data):
            cur = cur.next
            if cur is None:
                return False
        return True

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

 

노드 : 연결리스트의 기본 단위이고, data(저장할 데이터)와 next(다음 노드를 가리키는 참조)로 구성됨. 

파이썬에서 next는 다음 노드를 가리키는 객체의 주소를 저장함. (파이썬에는 포인터가 없지만, 변수에 객체 주소 저장가능)

insert 함수(tail 삽입) : 새로운 노드를 뒤에 삽입

delete 함수 : 특정 노드를 제거, 삭제 시에는 삭제 이전 노드의 next가 건너뛰도록 조정하고, head 삭제 시에는 다음 노드가 head가 되도록 구현함.

first = Node(2)
second = Node(3)
third = Node(4)

linkedlist = LinkedList()

linkedlist.insert(first)
linkedlist.insert(second)
linkedlist.insert(third)

linkedlist.print()

linkedlist.delete(third)
linkedlist.print()

코드 실행 결과 삽입, 삭제가 잘 작동함.

 

의문점

삭제 함수는 결국 시간복잡도가 O(n) 아닌가? 연결 리스트의 경우 위치를 알고 있으면 시간 복잡도는 O(1)이다. 반면, 배열은 위치를 알고 있어도 O(n)이다. 

삭제할 요소의 위치를 알 경우 : 연결 리스트 O(1), 배열 O(n)

삭제할 요소의 위치를 모를 경우 : 연결 리스트 O(n), 배열 O(n)

하지만, 삭제할 노드의 위치를 알고 있는 상황은 드물음. -> 연결 리스트의 이론적 장점이 현실에서는 자주 발휘되지 않는다.