[자료구조] 연결 리스트 (linked list)

연결 리스트

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

 

---

 

연결 리스트 구조

연결 리스트는 노드들의 집합이다. 노드는 데이터 필드와 링크 필드로 구성되어 있다.

 

📊 데이터 필드

데이터 필드에는 저장하고 싶은 데이터가 들어간다.

위 그림에서 하얀색 배경인 부분이 데이터 필드이다.

 

 

📎 링크 필드

링크 필드에는 다른 노드를 가리키는 포인터가 저장된다.

위 그림에서는 노란색 배경인 부분이 링크 필드이다.

 

연결 리스트에서는 연결 리스트의 첫 번째 노드를 알아야 만이 전체 노드에 접근할 수 있다.

따라서 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터라 한다.

 

그리고 마지막 노드의 링크 필드는 NULL로 설정되는데 이는 더 이상 연결된 노드가 없다는 것을 의미한다.

 

 

 

---

노드 생성

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

    Node()
    {
        data = 0;
        next = NULL;
    }

    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

연결 리스트를 생성하기 전, 노드를 먼저 생성해준다.

 

 

연결 리스트 생성

class Linkedlist
{
    Node *head;

public:
    Linkedlist() { head = NULL; } // 기본 생성자
    void insertNode(int); // 링크된 목록의 끝에 노드를 삽입
    void printList();     // 링크된 목록을 print
    void deleteNode(int); // 지정된 위치에서 노드를 삭제
};

 

---

 

➕ 삽입 연산 insert()

void Linkedlist::insertNode(int data)
{
    // 새 노드 생성
    Node *newNode = new Node(data);

    // 헤드에 할당
    if (head == NULL)
    {
        head = newNode;
        return;
    }
	
    Node *temp = head;
    
    //리스트 끝까지 이동
    while (temp->next != NULL)
    {
        temp = temp->next;
    }

    //맨 뒤에 삽입
    temp->next = newNode;
}

 

 

🖨 printList() 함수

void Linkedlist::printList()
{
    Node *temp = head;

    // 리스트가 비었는지 확인
    if (head == NULL)
    {
        cout << "List empty\n";
        return;
    }

    // 리스트 끝까지 출력
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

 

 

➖ 삭제 연산 delete()

void Linkedlist::deleteNode(int nodeOffset)
{
    Node *temp1 = head, *temp2 = NULL;
    int ListLen = 0;

    if (head == NULL)
    {
        cout << "List empty.\n";
        return;
    }

    // 연결 리스트의 길이를 찾는다
    while (temp1 != NULL)
    {
        temp1 = temp1->next;
        ListLen++;
    }

    // 삭제할 위치가 링크된 목록의 길이보다 작은지 확인
    if (ListLen < nodeOffset)
    {
        cout << "Index out of range\n";
        return;
    }

    temp1 = head;

    // 헤드 삭제
    if (nodeOffset == 1)
    {

        // Update head
        head = head->next;
        delete temp1;
        return;
    }

    // 삭제할 노드 서치
    while (nodeOffset-- > 1)
    {
        temp2 = temp1;
        temp1 = temp1->next;
    }

    // 이전 노드의 다음 포인터 변경
    temp2->next = temp1->next;

    // 노드 삭제
    delete temp1;
}

 

 

---

📌 전체 코드

#include <iostream>
using namespace std;

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

    Node()
    {
        data = 0;
        next = NULL;
    }

    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

class Linkedlist
{
    Node *head;

public:
    Linkedlist() { head = NULL; } // 기본 생성자
    void insertNode(int);         // 링크된 목록의 끝에 노드를 삽입
    void printList();             // 링크된 목록을 print
    void deleteNode(int);         // 지정된 위치에서 노드를 삭제
};

void Linkedlist::insertNode(int data)
{
    // 새 노드 생성
    Node *newNode = new Node(data);

    // 헤드에 할당
    if (head == NULL)
    {
        head = newNode;
        return;
    }

    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }

    //맨 뒤에 삽입
    temp->next = newNode;
}

void Linkedlist::printList()
{
    Node *temp = head;

    // 리스트가 비었는지 확인
    if (head == NULL)
    {
        cout << "List empty\n";
        return;
    }

    // 리스트 끝까지 출력
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << "\n";
}

void Linkedlist::deleteNode(int nodeOffset)
{
    Node *temp1 = head, *temp2 = NULL;
    int ListLen = 0;

    if (head == NULL)
    {
        cout << "List empty.\n";
        return;
    }

    // 연결 리스트의 길이를 찾는다
    while (temp1 != NULL)
    {
        temp1 = temp1->next;
        ListLen++;
    }

    // 삭제할 위치가 링크된 목록의 길이보다 작은지 확인
    if (ListLen < nodeOffset)
    {
        cout << "Index out of range\n";
        return;
    }

    temp1 = head;

    // 헤드 삭제
    if (nodeOffset == 1)
    {

        // Update head
        head = head->next;
        delete temp1;
        return;
    }

    // 삭제할 노드 서치
    while (nodeOffset-- > 1)
    {
        temp2 = temp1;
        temp1 = temp1->next;
    }

    // 이전 노드의 다음 포인터 변경
    temp2->next = temp1->next;

    // 노드 삭제
    delete temp1;
}

int main()
{
    Linkedlist list;

    list.insertNode(1);
    list.insertNode(2);
    list.insertNode(3);
    list.insertNode(4);

    cout << "리스트의 요소: ";

    list.printList();

    list.deleteNode(2);

    cout << "리스트의 요소: ";

    list.printList();
}

 

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!