01. Linked-List

링크드 리스트, 연결 리스트라고도 불리는 이 자료구조는

리스트를 이루고 있는 데이터의 [삽입], [삭제]가 빈번하거나

리스트의 크기가 정해져 있지 않은 경우에 주로 사용하는 자료구조입니다.

 

이러한 특징 때문에 [배열]과 자주 비교되곤 하는데요. 

이 포스트는 배열에 대해선 이미 어느 정도 알고 있다는 가정하에 쓰일 예정이기 때문에

혹시 배열에 대해 잘 모르시거나 복습이 필요하신 분은

아래 제가 예전에 네이버 블로그에 작성한 글을 참고해주시면 되겠습니다.

 

[자료구조 1강] 배열 (Array)

 

---

연결 리스트의 구조

 

 

연결 리스트의 노드(Node)

연결 리스트는 위 그림과 같이 데이터(Data) 필드와 링크(Link) 필드로 구성된 노드(Node)로 표현됩니다.

데이터 필드에는 저장하고자하는 데이터들을 저장하고 링크 필드에는 [다음 노드의 주소]를 저장합니다.

 

 

이렇게 노드에 다음 노드의 주소를 저장함으로써

계속해서 다음 노드를 찾을 수 있게 되고 리스트의 모습을 하게 됩니다.

 

//Linked List
struct Node{
    int data;
    Node* next;
};

 

data 필드에는 int형 data하나를 저장할 수 있는 변수가 있고

link 필드는 다음 노드의 주소를 저장할 수 있는 포인터 변수 하나가 있습니다.
('다음'노드를 가리킨다는 의미로 next라는 변수명을 썼습니다.)

 

---

연결 리스트를 쓰는 이유

 

인트로에서 언급했다시피 연결 리스트를 쓰는 이유는 크게 두 가지가 있습니다.

 

1. 크기가 정해져 있지 않다.

2. 삽입/삭제가 빠르다

 

[1.크기가 정해져있지 않다.]는 연결 리스트는 새로운 데이터가 필요할때마다

새로운 노드를 만들어서 연결 리스트에 잘 연결만 시켜주면 됩니다.

그렇기 때문에 최대 크기를 알 수 없는 경우에 주로 사용합니다.

 

[2. 삽입/삭제가 빠르다]는 중간에 데이터를 삽입하거나 삭제할때

배열처럼 데이터의 이동이 필요없기 때문입니다.

그렇기 때문에 데이터 사이사이에 데이터의 삽입/삭제가 빈번할때 주로 사용합니다.

 

 

 

---

연결리스트에 데이터 추가하기

 

연결 리스트에 데이터를 추가하는 방법을 살펴보기에 앞서 지금 설명하는 연결 리스트는

단일 연결 리스트(Single Linked List)라는 점을 알려드립니다.

(링크 필드가 하나인 연결 리스트를 단일 연결 리스트라고 부릅니다.)

 

먼저 비어있는 리스트 상황을 그려보겠습니다.

 

리스트의 시작부분을 [head]라고 하고

리스트의 끝부분 [0(NULL)]로 지정합니다. 

Node* head = 0; //NULL

 

동적할당을 통해 새로운 노드를 하나 생성하고 데이터를 넣어보겠습니다.

Node *newNode = new Node;
newNode->data = 1;

 

새로운 노드를 만들었고 데이터까지 저장했다면 이제 노드를 리스트에 연결시켜줘야 의미가 있습니다.

그런데 리스트가 아직까진 비어있기 때문에 head가 newNode가 되고 newNode의 next는 0이되면 됩니다.

newNode->next = 0;
head = newNode;

 

그럼이제 다시 새 노드를 추가해봅시다.

newNode = new Node;
newNode->data = 2;

 

이번에는 연결 리스트가 비어있지 않습니다.

연결 리스트가 비어있지 않을때는 새로운 노드를 head에 연결하고 head를 새로운 노드로 바꿔줍니다.

newNode->next = head;
head = newNode;

 

그럼 지금까지 한 내용을 토대로 연결리스트 구조체를 구현해 보겠습니다.

 

struct Node{
    int data;
    Node* next;
}

struct List{
    Node* head;

    List(){
        head=0;
    }
    
    void add(int data){
        Node* newNode = new Node;
        newNode->data = data;

        if(head == 0){ //리스트가 비어있다면
            newNode->next = 0;
        }
        else{
            newNode->next = head;
        }
        head = newNode;
    }
}

 

---

더미 노드의 활용

앞서 설명한 데이터 추가방법은 연결 리스트가 비었을때, 비어있지 않을때를 구별해서 구현을 했어야했습니다.

 

이러한 방식의 구현은

아직 설명하진 않았지만 앞으로 탐색,삭제 등등 앞으로 구현해야할 많은 부분들도

연결 리스트가 비었을때 아닐때를 구분해서 구현해야한다는 불편함이 있습니다.

 

이를 해결하기 위해서 [더미]노드라는

존재하지만 데이터는 저장하지 않는(저장하는 행위 자체가 의미없는)

임시 노드를 하나 생성해서 head로 지정해놓으면

연결 리스트는 [항상 비어있지 않는 상태]가 됩니다.

 

struct Node{
    int data;
    Node* next;
}

struct List{
    Node* head;

    List(){
        head = new Node;
        head->next = 0;
    }
    
    void add(int data){
        Node* newNode = new Node;
        newNode->data = data;
        newNode->next = head;
        
        head->next = newNode;
    }
}

 

이렇게 더미노드의 활용은 코드를 통일시켜서 안정성(Stable)을 높여주기도 합니다.

 

 

---

연결 리스트가 뭔지, 왜쓰는지, 어떻게 구현하는지, 그리고 더미노드의 활용에 대해서 설명을 했습니다.

다음에는 연결 리스트의 탐색, 삭제에대해 살펴보겠습니다.

 

이해가 안되거나 추가 설명이 필요하거나 궁금하신 부분은 댓글 남겨주시면 답변드리겠습니다.

감사합니다.