[자료구조] 배열과 연결 리스트

Minjun Kim

11 May 2025 • 4 min read

Thumbnail: Photo by Frank van Hulst (Unsplash)

다른 추상 자료형(Abstract Data Type)을 구현할 때 기반이 되는 기초적인 선형 자료구조인 배열과 연결 리스트에 관해 간단히 정리해봤습니다.

배열

배열은 동일한 자료형의 원소들을 연속적인 메모리 공간에 저장하는 선형 자료 구조입니다. 배열의 크기는 고정되어 있어서, 선언 시에 크기를 지정해야 합니다. (어떤 자료형을 몇개 담을 것인지)

int array[5] = {1, 2, 3, 4, 5};

연결 리스트 (Linked List)

연결 리스트는 선형 자료구조로, 배열과 비슷하지만 구현 방식이 다릅니다.

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하고 관리합니다. 아래 표로 연결 리스트와 배열의 차이점을 비교해보겠습니다.

특징	배열	연결 리스트
메모리 주소	물리 메모리 상에서 연속	물리 메모리 상에서 연속 X
삽입/삭제	O(N) : 배열을 순회해서 값을 찾아야 한다	O(1) : 포인터만 수정하면 된다
접근	O(1) : 인덱스가 곧 메모리 주소이다	O(N) : 노드를 따라 값을 찾아야 한다

연결 리스트의 종류

연결 리스트는 노드 간의 연결 방식에 따라 크게 3가지로 나뉩니다.

단일 연결 리스트
이중 연결 리스트
원형 연결 리스트

가장 간단한 단일 연결 리스트의 구현에 대해 알아보겠습니다.

Python으로 구현되었습니다. 클래스 이름 뒤의 [T]는 제네릭 구문으로, 다른 언어의 제네릭 구문과 비슷한 기능을 합니다.

class Node[T]:
    """단방향 연결 리스트의 노드 클래스"""
    value: T
    next: "Node[T] | None"

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

class List[T]:
    """단방향 연결 리스트"""
    head: Node[T]  # 연결 리스트의 제일 첫 노드의 포인터
    end: Node[T]   # 연결 리스트의 제일 마지막 노드의 포인터

    def __init__(self, value: T | None = None):
        self.head = Node[T](value) if value is not None else None
        self.end = None

    def append(self, value: T):
        """연결 리스트의 맨 끝에 새 노드를 추가한다."""
        if self.head is None:
            self.head = Node[T](value)
            self.end = self.head
        else:
            self.end.next = Node[T](value)
            self.end = self.end.next

    def delete(self, idx: int):
        """연결 리스트의 idx번째 노드를 삭제한다."""
        prev: Node[T] = self.head
        for i in range(1, idx-1):
            prev = prev.next

            # idx가 연결 리스트의 길이보다 크면 예외 발생
            if prev is None:
                raise IndexError("Index out of range")
        
        node = prev.next
        prev.next = node.next
        del node

    def insert(self, idx: int, value: T):
        """연결 리스트의 idx번째에 새 노드를 삽입한다."""
        node: Node[T] = self.head
        for i in range(1, idx):
            node = node.next

            # idx가 연결 리스트의 길이보다 크면 예외 발생
            if node is None:
                raise IndexError("Index out of range")
        
        next = node.next
        node.next = Node[T](value, next)
    
    def index(self, value: T) -> int:
        """연결 리스트에서 value의 인덱스를 반환한다. 없으면 -1을 반환한다."""
        node: Node[T] = self.head
        idx = 0
        while node is not None:
            if node.value == value:
                return idx
            node = node.next
            idx += 1
        return -1

    def length(self) -> int:
        """연결 리스트의 길이를 반환한다."""
        node: Node[T] = self.head
        count = 0
        while node is not None:
            count += 1
            node = node.next
        return count
    
    def __iter__(self):
        """연결 리스트를 순회할 수 있도록 해준다."""
        node: Node[T] = self.head
        while node is not None:
            yield node.value
            node = node.next

single_list = List[int]()

for i in range(1, 11):
    single_list.append(i)

for n in single_list:
    print(n.value, end=" ")
print()

idx = single_list.index(5) # 값이 5인 노드의 인덱스 탐색
print(idx)
single_list.delete(idx)

for n in single_list:
    print(n.value, end=" ")
print()

print(single_list.length()) # 연결 리스트의 길이 탐색

linked_list.py