자료구조 - 연결 리스트(Linked List)

연결 리스트(Linked List) 이란?

 

 

연결 리스트(Linked List)는 데이터를 노드(Node)라는 단위로 관리하는 자료구조입니다. 각 노드는 두 가지 정보를 담고 있습니다. 첫 번째로는 실제로 저장하고자 하는 데이터(예를 들어, 정수, 문자열 등)를 가지고 있고, 두 번째로는 다음 노드를 가리키는 포인터(Pointer)를 갖습니다.

 

이러한 연결 리스트의 구조는 각 노드가 메모리의 임의의 위치에 위치할 수 있다는 특징을 가집니다. 즉, 각 노드들은 메모리의 어떤 곳이든지 분산되어 있을 수 있습니다. 이와 달리 배열(Array)은 연속적인 메모리 공간에 데이터가 순차적으로 저장되며, 각 요소들은 인덱스를 통해 접근됩니다.

 

연결 리스트에서 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함하고 있습니다. 이 포인터를 통해 다음 노드의 위치를 알 수 있습니다. 따라서 연결 리스트에서는 각 노드가 다음 노드를 가리키는 방식으로 리스트가 연결되어 있습니다. 이것이 바로 "연결" 리스트의 이름이 유래된 이유입니다.

 

이와 반대로, 배열에서는 각 요소가 메모리에 연속적으로 저장되어 있기 때문에 인덱스를 통해 해당 요소에 접근할 수 있습니다. 하지만 배열은 크기가 고정되어 있기 때문에 삽입 또는 삭제가 발생할 때 요소들을 이동시키는 등의 비용이 발생할 수 있습니다. 반면 연결 리스트에서는 삽입 또는 삭제가 발생해도 다른 노드들의 위치를 변경할 필요가 없기 때문에 이러한 비용이 발생하지 않습니다.

 

이렇듯, 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 통해 서로 연결되어 있는 구조를 가지고 있으며, 이러한 특성으로 인해 배열과는 다른 동작 방식을 갖습니다.

 

연결 리스트 코드 예시 (C#)

아래 코드는 C#에서 연결 리스트를 구현한 예시입니다.

using System;

public class Node
{
    public int data;
    public Node next;

    public Node(int d)
    {
        data = d;
        next = null;
    }
}

public class LinkedList
{
    Node head;

    public void PrintList()
    {
        Node n = head;
        while (n != null)
        {
            Console.Write(n.data + " ");
            n = n.next;
        }
    }

    // 코드 예시에 문제 설명이 추가됨
    public void AddNode(int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            head = newNode;
            return;
        }
        Node lastNode = head;
        while (lastNode.next != null)
        {
            lastNode = lastNode.next;
        }
        lastNode.next = newNode;
    }
}

class Program
{
    static void Main(string[] args)
    {
        LinkedList linkedList = new LinkedList();
        linkedList.AddNode(1);
        linkedList.AddNode(2);
        linkedList.AddNode(3);

        Console.WriteLine("Linked List 출력:");
        linkedList.PrintList();
    }
}

 

위 코드를 실행한 결과는 다음과 같습니다.

 

Linked List 출력:
1 2 3

 

 

 

연결 리스트의 장단점

 

- 장점

• 데이터의 삽입과 삭제가 용이하다. 중간에 요소를 추가하거나 삭제할 때 다른 요소들의 이동이 필요 없다.
• 메모리 관리가 유연하다. 연결 리스트는 동적으로 크기를 조절할 수 있다.

- 단점

• 임의의 노드에 접근하기 위해서는 처음부터 순차적으로 탐색해야 한다. 이는 탐색 속도가 느리다는 것을 의미한다.
• 각 노드가 포인터를 저장하기 때문에 메모리 공간이 더 필요하다.

 

연결 리스트 사용 사례

 

• 데이터의 삽입과 삭제가 빈번한 경우에 사용된다. 예를 들어, 스택이나 큐와 같은 추상 자료형을 구현할 때 많이 사용된다.
• 데이터의 저장 순서가 중요한 경우에 사용된다. 예를 들어, 웹 브라우저의 방문 기록이나 편집기의 undo 기능과 같은 기능을 구현할 때 사용될 수 있다.

 

연결 리스트는 데이터의 동적인 추가 및 삭제가 빈번한 상황에서 효율적으로 사용될 수 있는 자료구조입니다. 하지만 임의의 요소에 접근하는데에는 선형적인 탐색이 필요하므로 데이터 접근 속도가 느릴 수 있습니다. 따라서 사용 시에는 이러한 장단점을 고려하여 적절히 활용해야 합니다.