Skip to content

Latest commit

 

History

History
244 lines (195 loc) · 5.29 KB

15.linkedlist.md

File metadata and controls

244 lines (195 loc) · 5.29 KB
Raw

링크드리스트

자료구조의 한 종류입니다. (자료구조 : 데이터 관리하는 방법)

링크드리스트는 데이터 목록을 연결시켜서 접근할 수 있는 구조를 나타내고 있고 , 데이터를 저장하기위한 노드가 있으므로 다음 노드의 위치를 알 수 있습니다.

리스트는 선형구조로 되어있으며, 배열처럼 바로 접근되지는 않습니다.

그러므로 무조건 앞에서부터 차례대로 들어가야합니다.

그러나 처음과 끝만 연결해주면 되기때문에 갯수의 제한이 없어 자주 사용하게됩니다.

용어 정리

  1. Node: 숫자(데이터)를 담은 세트
  2. Head: 첫 Node
  3. Tail: 마지막 Node

노드 구조체 정의

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

node라는 구조체를 만듭니다.

링크드리스트 생성

class list {
private:
    node *head, *tail;
public:
    list() {
        head = NULL;
        tail = NULL;
    }
};

class에 대한 자세한 내용은 향후 클래스 파트에서 더 배울 수 있습니다.

이 곳에서는 list라는 클래스로 링크드리스트를 생성한다고 이해하면 됩니다.

삽입(Insertion)

배열과 달리 삽입할 위치의 앞, 뒤 노드(Node)의 화살표만 수정해주면 가볍게 삽입을 할 수 있습니다.

    void create(int value) {
        node *temp = new node;
        temp->data = value;
        temp->next = NULL;
        if (head == NULL) {
            head = temp;
            tail = temp;
            temp = NULL;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
        cout << "creating " <<value<< endl;
    }

링크드리스트에 차례대로 노드를 생성합니다.

    void insert(int value) {
        node *temp = new node;
        temp->data = value;
        temp->next = head;
        head = temp;
        cout << "inserting " << value << endl;
    }

링크드리스트 앞에 값을 삽입합니다.

삭제(Removal)

삭제의 경우 삽입의 정확한 반대를 해주면 됩니다.

    void del_first() {
        node *temp = new node;
        temp = head;
        head = head->next;
        delete temp;
        cout << "deleting first number" << endl;
    }
    void del_end() {
        node *prev = new node;
        node *curr = new node;
        curr = head;
        while (curr->next != NULL) {
            prev = curr;
            curr = curr->next;
        }
        tail = prev;
        prev->next = NULL;
        delete curr;
        cout << "deleting end number" << endl;
    }

탐색(Traversal)

특정한 노드를 방문하고 싶으면 처음부터 시작해서 화살표를 따라가며 방문해야 됩니다.

        for (int i = 1; i < pos; i++) {
            prev = curr;
            curr = curr->next;
        }

탐색은 특정 부분 삽입과 삭제에 다양하게 쓰이기 때문에 코드의 일부만 가져왔습니다.

출력(Print)

탐색과 유사하게 머리부터 다음꺼로 넘어가면서 출력합니다.

    void display() {
        node *temp = new node;
        temp = head;
        while (temp!=NULL)
        {
            cout <<"|"<< temp->data << "|" ;
            temp = temp->next;
        }
        cout << endl;
    }

포인터 초기화

포인터는 초기화할때 null로 넣어 주어야합니다.

list()
{
    head=NULL;
    tail=NULL;
}

위 예시 코드에서 설명해보자면, 생성자로 머리와 꼬리를 초기화합니다.

더블 링크드리스트

각 노드가 자신의 앞과 뒤에 노드를 가리킵니다.

기존의 노드 구조체에 이전 노드도 같이 정의합니다.

struct node
{
    int data;
    node *next;
    node *prev;
};

(더블 링크드리스트에 대한 자세한 실습은 추후 공지하겠습니다.)

과제

  • 과제-1(1) : 싱글 링크드리스트에 대한 구조를 그림판을 그리기

  • 과제-1(2) : 더블 링크드리스트에 대한 구조를 그림판을 그리기

  • 과제-2 : 한 링크드리스트의 모든 노드를 삭제하는 코드 작성하기

예제 코드:

#include<iostream>

using namespace std;

struct node
{
    int data;
    node *next;
};
class list {
private:
    node *head, *tail;
public:
    list() {
        // 링크드리스트를 초기화하는 코드를 작성합니다.
    }
    void display() {
        node *temp = new node;
        temp = head;
        while (temp!=NULL)
        {
            cout <<"|"<< temp->data << "|" ;
            temp = temp->next;
        }
        cout << endl;
    }
    void create(int value) {
        node *temp = new node;
        temp->data = value;
        temp->next = NULL;
        if (head == NULL) {
            head = temp;
            tail = temp;
            temp = NULL;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }
    void del_all() {
        // 모든 노드를 지우는 코드를 작성합니다.
    }
};
int main() {
    list a;
    a.create(5);
    a.create(10);
    a.create(15);
    a.create(20);
    a.display();
    a.del_all(); //ASSIGNMENT "del_all()"
    a.display();

    return 0;
}
  • 과제-2(1) : 싱글 링크드리스트로 삽입,삭제,탐색을 활용한 프로그램 만들기