선형구조 연결 리스트의 기본 원리와 종류

선형구조 연결 리스트의 기본 원리와 종류

 

 

컴퓨터 과학에서 데이터 구조는 정보를 효율적으로 저장, 관리, 처리하기 위한 기본적인 구성 요소입니다. 특히, 연결 리스트는 데이터를 선형으로 저장하는 기본적인 구조 중 하나로, 다양한 프로그래밍 상황에서 유용하게 사용됩니다. 이 글에서는 연결 리스트의 개념, 종류, 그리고 구조체를 이용한 구현 방법을 알아보며, 프로그래밍에서의 연결 리스트 활용의 중요성을 이해할 것입니다.

 

 

연결 리스트에 대해

 

연결 리스트는 일련의 연결된 노드를 포함하는 선형 데이터 구조로, 각 노드가 데이터 항목과 다음 노드의 주소를 포함합니다. 이 구조는 데이터의 동적 추가 및 삭제가 용이하며, 미리 공간을 할당하지 않아도 되는 이점이 있습니다.

 

 

단일 연결 리스트(Single Linked List)

https://gusdnd852.tistory.com/100

 

단일 연결 리스트는 각 노드가 다음 노드만을 가리키는 가장 기본적인 형태의 연결 리스트입니다. 다음 노드의 주소를 저장하는 포인터(또는 참조)와 데이터를 함께 저장합니다.

 

연결 리스트의 구현

연결 리스트는 주로 구조체를 이용하여 C 언어에서 구현됩니다. 각 노드는 데이터를 저장하는 부분과 다음 노드의 주소를 가리키는 포인터로 구성됩니다.

 

 

연결 리스트의 기본 구조

연결 리스트는 데이터 요소(노드)들이 포인터를 통해 순차적으로 연결된 구조를 가지고 있습니다. 각 노드는 데이터 필드와 하나 이상의 '다음' 노드를 가리키는 포인터(링크) 필드로 구성됩니다.

 

 

예시 코드

struct Node {
    int data;
    Node* next;
};

 

 

연결 리스트에서의 작업

 

삽입과 삭제

연결 리스트에서의 삽입과 삭제 작업은 상대적으로 간단합니다. 삽입할 때는 새 노드의 포인터를 이전 노드와 다음 노드에 연결시키고, 삭제할 때는 삭제하고자 하는 노드를 건너뛰어 이전 노드와 다음 노드를 직접 연결하면 됩니다.

 

요소 추가하기

연결 리스트에 요소를 추가하는 과정은 다음과 같습니다.

1) head에 추가하기: 새 노드를 생성하고, 이 노드의 다음 포인터를 현재 머리로 설정한 다음, 리스트의 머리를 이 새 노드로 업데이트합니다.

void addHead(Node*& head, int value) {
    Node* newNode = new Node{value, head};
    head = newNode;
}

 

2) tail에 추가하기: 새 노드를 생성하고, 리스트의 마지막 노드를 찾은 다음, 이 마지막 노드의 다음 포인터를 새 노드로 설정합니다.

void addTail(Node* head, int value) {
    Node* newNode = new Node{value, nullptr};
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

 

3) 중간에 추가하기: 특정 위치에 새 노드를 추가하기 위해서는, 먼저 해당 위치의 이전 노드를 찾아야 합니다. 그 다음, 새 노드의 다음 포인터를 이전 노드의 다음 노드로 설정하고, 이전 노드의 다음 포인터를 새 노드로 설정합니다.

 

요소 삭제하기

연결 리스트에서 요소를 삭제하는 방법은 다음과 같습니다.

1) head에서 삭제하기: 리스트의 머리를 머리 노드의 다음 노드로 업데이트합니다.

 

2) tail에서 삭제하기: 리스트의 마지막에서 두 번째 노드를 찾아 그 노드의 다음 포인터를 null로 설정합니다.

 

3) 중간에서 삭제하기: 삭제하려는 노드의 이전 노드를 찾아, 그 노드의 다음 포인터를 삭제하려는 노드의 다음 노드로 업데이트합니다.

void deleteNode(Node*& head, int key) {
    Node* temp = head, *prev = nullptr;
    if (temp != nullptr && temp->data == key) {
        head = temp->next;
        delete temp;
        return;
    }
    while (temp != nullptr && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == nullptr) return;
    prev->next = temp->next;
    delete temp;
}

 

 

검색과 정렬

연결 리스트에서의 검색은 시작 노드부터 순차적으로 데이터를 비교하면서 진행합니다. 정렬도 가능하지만, 배열 기반의 리스트에 비해 상대적으로 느릴 수 있습니다.

순회

연결 리스트의 순회는 시작 노드에서부터, 각 노드의 포인터를 따라 다음 노드로 이동하면서 진행됩니다. 일반적으로 while문이나 for문을 사용하여 리스트의 끝에 도달할 때까지 반복합니다.

 

코드 예시

// 간단한 연결 리스트의 노드 구조체 예시
struct Node {
    int data;      // 데이터 필드
    struct Node* next; // 다음 노드를 가리키는 포인터
};

 

이러한 기본적인 노드 구조를 바탕으로, 연결 리스트에서 다양한 작업을 수행할 수 있습니다.

 

 

이중 연결 리스트(Double Linked List)와 순환 연결 리스트(Circular Linked List)

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드의 주소를 모두 가지고 있는 형태로, 양방향 탐색이 가능합니다. 순환 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 형태로, 리스트의 끝에서 시작으로 쉽게 돌아갈 수 있습니다.

 

 

연결 리스트의 활용

연결 리스트는 그 유연성과 다양한 변형으로 인해 알고리즘, 운영체제, 네트워크 통신 등 다양한 컴퓨터 과학 분야에서 광범위하게 활용됩니다. 특히 메모리 관리와 데이터 처리의 효율성을 높이는 데 중요한 역할을 하며, 앞으로도 그 활용도는 계속해서 증가할 것으로 예상됩니다.

 

---

 

끝으로

연결 리스트는 데이터를 동적으로 관리할 수 있는 유연한 구조를 제공합니다. 각 노드가 데이터와 다음 노드의 주소를 가지고 있어, 데이터의 추가와 삭제가 용이한 특징을 가집니다. 프로그래밍에서 연결 리스트를 이해하고 활용하는 것은 효율적인 데이터 관리와 알고리즘 구현에 있어 필수적입니다. 이 글을 통해 연결 리스트의 기본적인 개념과 구현 방법을 이해하고, 여러분의 프로그래밍 실력 향상에 도움이 되길 바랍니다. 유익한 시간 되시길 바랍니다.

 

▼ 자료구조의 다른 글 ▼

 

많은 기업들이 자료구조와 알고리즘을 중시하는 이유