Coding/알고리즘

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

Dev_Klare 2023. 11. 26. 21:09

List - 리스트

  • 데이터들을 정해진 순서대로 일렬로 나열한 것
  • 리스트의 구현 방법에 따라 크게 순차 리스트, 연결 리스트로 나뉨
  • 해당 글에서는 연결 리스트만을 다룸

원소(데이터)들을 순서대로 나열해 둔 자료구조를 '리스트'로 정의할 수 있다.

흔히 '버킷 리스트(Bucket List)', '체크 리스트 (Check List)'와 같이 1번 ~~~, 2번 ~~~ 의 형태로 정리되어 있는 것을 생각할 수 있는데, 컴퓨터의 자료구조에서도 비슷하게 작동한다.

1번 원소, 2번 원소, 3번 원소.... 와 같은 순차적으로 정의되어 있는 원소들을 하나로 묶어둔 것을 '리스트'라고 합니다.

 

'배열'과 '리스트'는 혼동할 수 있지만 다른 개념입니다.

'배열'은 자료형 (Data Type)의 이름이고, '리스트'는 자료구조 (Data Structure)의 이름입니다.

 

Linked List - 연결 리스트

해당 글에서는 연결 리스트에 대하여 집중적으로 다루도록 한다.

연결 리스트는 영어로 Linked List라고 한다.

다른 사이트의 주소로 바로 이동할 수 있게 해주는 기능을 '하이퍼링크(HyperLink)'라고 부르듯이

연결 리스트는 바로 다음 노드(원소)로 이동할 수 있게 해주는 '링크'라는 값을 가진다.

따라서 맨 처음 노드(원소)의 위치만 기억하고 있다면 리스트 전체에 접근할 수 있다.

연결 리스트는 노드들끼리의 연결 모습에 따라 단순 연결 리스트, 이중 연결 리스트, 순환 연결 리스트로 나눌 수 있다.

※ 위 그림에서는 주소값의 이해를 돕기위해 임의 정수로 표현했지만, 실제 주소값은 위 처럼 저장되지 않습니다.

연결 리스트는 보물 찾기를 예로 들 수 있다.

첫 번째 보물의 위치가 있는 보물 지도를 가지고 시작하여, 첫 번째 보물 위치에는 보물(데이터)과 두 번째 보물지도(포인터)가 함께 존재한다. 두 번째 보물 지도를 보고 그다음 보물을 찾으면 역시 보물(데이터)과 그다음 보물지도(포인터)가 존재하여 보물(데이터)을 순서대로 하나씩 찾아가는 것이다. (탐색)

첫 번째 보물과 두 번째 보물 사이에 한 개의 보물을 더 추가하고 싶다면 첫 번째 보물위치에 추가할 보물 지도를 놓고, 추가한 보물 위치에 두 번째 보물지도를 놓으면 된다. (삽입)

만약 두 번째 보물이 더 이상 필요 없다면, 세 번째 보물지도를 첫 번째 보물 위치에 숨김으로써 두 번째 보물을 없는 것으로 만들 수 있다. (삭제)

관련 용어 정리

데이터(Data) - 연결 리스트의 각 원소의 실질적인 자료 값. 데이터 필드라고 부름

링크(Link) - 연결 리스트의 각 원소에서 다음 원소의 주소 값(위치). 링크 필드라고 부름

노드(Node) - 연결 리스트의 각 원소 (데이터 + 링크)

헤드(Head) - 리스트의 첫 번째 노드

테일(Tail) - 리스트의 마지막 노드

특징

  1. 다음 노드의 위치(주소값)를 이전 노드가 저장하고 있다.
  2. 다양한 자료 구조의 구현 방법으로 사용된다.

1. 노드들끼리 물리적인 순서대로 나열되어 있는 것이 아닌, 메모리상의 랜덤한 위치에 노드를 생성하고, 이전에 있던 노드가 다음 노드의 위치(메모리상의 주소값)를 기억하고 있는 형태이다.

2. 연결 리스트를 그대로 사용하지는 않을지라도, '이전 노드에 다음 노드의 주소를 저장한다'라는 개념은 큐(Queue), 트리(Tree), 그래프(Graph) 자료구조에서 사용된다. 노드와 링크(포인터)의 개념만 확실히 알아두어도 많은 자료구조의 이해에 도움이 될 것이다.

장점

  1. 노드의 삽입, 삭제의 실행 시간이 짧다.
  2. 메모리 관리에 용이하다.

1. 노드를 삽입, 삭제하는 경우, 링크 값의 변경이 필요한 노드의 링크만 수정하면 되기 때문에 짧은 실행 시간으로 연산이 가능하다.

2. 미리 크기를 선언할 필요 없이 필요할 때 새 노드를 생성하고, 삭제 시에 기존 노드를 메모리에서 소멸하기 때문에 필요한 만큼만 메모리사용이 가능하다.

 

단점

  1. 데이터의 탐색 속도가 느리다.
  2. 원하는 노드에 임의 접근이 불가능하다.
  3. 데이터 손상에 취약하다.

1. 필요한 데이터를 찾기 위해서는 헤드 노드부터 링크를 통해 노드를 일일이 확인하며 원하는 데이터 값을 찾아야 하기 때문에, 탐색을 자주 해야 하는 경우에 연결 리스트가 실행 시간을 증가시키는 원인이 될 수 있다. 특정 알고리즘을 활용하여 탐색 속도를 향상할 수 있으나, 이번 글에서는 제외하기로 한다.

2. 인덱스라는 개념이 있다 하더라도, 물리적으로 데이터가 여기저기 흩어져있기 때문에 인덱스를 통한 저장위치의 예측이 불가능하기 때문에 결국 탐색을 통하여 노드에 접근해야 한다.

3. 헤드 노드의 위치를 잃어버리면 리스트 전체에 접근할 수 없게 되고, 하나의 노드만 손상되어도 그다음 노드를 찾을 수 없어 리스트 전체가 손상되는 일이 발생할 수 있다.

데이터 다루기

연결 리스트에서는 데이터를 노드 단위로 다루게 된다.

특정 데이터 값을 삽입하기 위해서는 노드를 하나 삽입해야 하며, 삭제할 때도 노드를 하나 삭제해야 한다.

탐색

연결 리스트는 인덱스라는 개념을 적용할 수 있을지라도, 인덱스를 통한 데이터의 접근이 불가능하다.

따라서 원하는 데이터 값을 찾기 위해서는 헤드부터 시작하여 링크를 통해 노드를 하나씩 거쳐가며 값을 찾아야 한다.

삽입

연결 리스트에 새로운 데이터를 삽입하는 경우 새 노드를 생성해야 한다.

먼저 탐색 과정을 통하여 원하는 위치를 찾는다. (원하는 위치 바로 앞 노드를 찾아야 한다.)

새 노드를 생성한 다음, 원하는 위치의 이전 노드가 새 노드를 가리키게 하고, 새 노드의 링크가 다음 노드를 가리키게 만드는 것으로 구현할 수 있다.

이때, 연결 리스트에 인덱스를 간접적으로 표현하기 위해 변수를 설정하는 방법을 많이 사용한다. (변수 pos)

삭제

삽입과 비슷한 방법으로 삭제하려는 노드의 바로 이전 노드의 링크를 다음 노드를 가리키게 한다.

이후, 더 이상 사용하지 않는 노드는 메모리에서 삭제하여 메모리 효율을 높인다.

구현

C++에서는 구조체를 활용하여 구현할 수 있다.

Python과 Java에서는 class를 활용하여 구현하는 경우가 많다.

※ 자료구조의 구현 방법은 코드 제작자에 따라 다르기 때문에 참고용으로만 봐주시기 바랍니다.

#include<bits/stdc++.h>
using namespace std;

// 연결 리스트의 노드를 정의
struct node{
    char data='\0';
    node *link=NULL;
};
// 연결 리스트의 Head 노드를 전역변수로 정의
node *Head=(node*)malloc(sizeof(node));

// 연결 리스트를 출력하는 함수
void printList(){
    node *curr=Head;
    while(curr->link!=NULL){
        cout<<curr->data<<' ';
        curr=curr->link;
    }
    cout<<curr->data<<'\n';
}

// 문자 c를 리스트의 target 번째에 삽입
// target을 입력하지 않았거나 유효하지 않으면 맨 뒤에 삽입
void Insert(char c, int target=0){
    node *curr=Head,*New=(node*)malloc(sizeof(node));
    New->data=c;
    
    // target==1 이라면 Head가 바뀌므로 예외처리
    if(target==1){
        New->link=Head;
        Head=New;
        return;
    }
    
    // Tail 노드나 target번째 노드 앞을 찾을 때까지 반복
    int pos=1;
    while(curr->link!=NULL && pos!=target-1){
        curr=curr->link;
        pos++;
    }
    New->link=curr->link;
    curr->link=New;
}

// 리스트의 target번째 노드를 삭제
// target을 입력하지 않았거나 유효하지 않으면 Tail 노드를 삭제
void Delete(int target=0){
    node *curr=Head;
    if(target==1){
        Head=curr->link;
        free(curr);
        return;
    }
    
    // Tail 노드나 target번째 노드 앞을 찾을 때까지 반복
    int pos=1;
    while(curr->link!=NULL && pos!=target-1){
        if(target==0 && curr->link->link==NULL)
            break;
        curr=curr->link;
        pos++;
    }
    node *del=curr->link;
    curr->link=del->link;
    free(del);
}

int main(){
    // A,B,C,D,E 로 이루어진 연결 리스트를 만듬
    Head->data='A';
    for(int i=1; i<5; i++)
        Insert('A'+i);
    printList();
    
    // 3 번째에 G를 삽입
    Insert('G',3);
    printList();
    
    // 마지막 노드를 삭제
    Delete();
    printList();
    
}

 

 

코드의 실행 결과

A B C D E
A B G C D E
A B G C D

 

맺음말

연결 리스트 자체를 문제풀이 중에 직접 사용하는 일은 거의 없습니다.

C++ 언어의 경우 표준 템플릿 라이브러리에서 제공하는 vector, queue, stack, set, map 등의 컨테이너를 훨씬 많이 사용하게 될 겁니다.

하지만 노드와 링크로 이루어진 구조를 이해하고 있는 것과 모르는 것에는 메모리의 구조나 활용, 코드의 이해 부분에서 큰 차이가 있을 것이므로 꼭 숙지하셨으면 좋겠습니다.

다음 글에서는 스택 (Stack)에 대하여 소개하겠습니다.

저작자표시 비영리 변경금지 (새창열림)