[자료구조] Single Linked List

📌 단일 연결 리스트

• 단방향 연결리스트
  
  
• head가 있고 다음 요소를 가리키는 next 포인터가 있기 때문에, 앞에서 뒤로만 탐색이 가능하다
  
  
• 배열과 달리, 크기가 동적으로 변할 수 있다 (동적 메모리 할당) -> 메모리 공간을 효율적으로 사용할 수 있음
  
  
• 항상 head부터 순차적으로 원하는 위치로 접근

✅ private에서 변수와 구조체 정의 & 생성자에서 초기화

• Node 구조체
  -> 리스트의 각 요소를 의미함
  -> data 는 노드가 저장하는 실제 값
  -> Node * next 는 현재 노드의 바로 다음 노드를 가리키는 포인터 (마지막 노드는 nullptr)
  

• 노드의 크기를 정해줄 size변수

• 연결리스트의 첫번째 Node를 가리키는 head 포인터

• 🟥 class를 template typename T로 지정하여 메인함수에서 자료형 정하게 해둠

#include <iostream>

using namespace std;

template <typename T>
class SingleLinkedList
{
private:
    int size;

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

    Node* head;

public:
    // 생성자
    SingleLinkedList()
    {
        size = 0;
        head = nullptr;
    }

---

✅ PushFront ( ) 함수 (앞에 데이터 넣기)

• 노드가 하나도 없을 때
  
  

• head가 nullptr을 가리키고 있으면 노드가 비어있다는 것

• newnode를 동적으로 생성한 뒤 head가 newnode를 가리키게 함

• newnode에 데이터를 넣고 newnode -> next 는 nullptr을 가리키게 함

• 노드가 여러개 일때
  
  

• newnode를 동적으로 생성한 뒤 data값을 넣고 newnode -> next를 head로 가리키게 함
  
  

• head 의 위치를 newnode로 옮겨주기
  

• 마지막으로 노드의 size ++

// 앞에 값 넣기
void PushFront(T data)
{
    // 객체를 동적할당 후 포인터로 객체 접근
    Node* newnode = new Node;

    // 노드가 하나도 없을때
    if (head == nullptr)
    {
        head = newnode;

        head->data = data;
        head->next = nullptr;
    }
    // 노드가 여러개 일때       
    else
    {
        newnode->data = data;
        newnode->next = head;

        head = newnode;
    }
    size++;
}

---

✅ PopFront ( ) 함수 (앞에 데이터 빼기)

• 노드가 하나도 없을 때
  
  

• head가 nullptr을 가리키고 있으면 노드가 하나도 없다는 뜻인데, 이 상태에서는 데이터를 뺄 수 없다
  

• 노드가 하나 이상있을 때
  
  

• deleteNode 포인터를 생성하고 head를 가리키게 함
  

• head의 위치를 deleteNode의 next로 이동시키고 deleteNode가 가리키는 곳 delete
  

• 데이터를 하나 뺏으니 size --

// 앞에 값 빼기
void PopFront()
{
    // 노드가 하나도 없을때
    if (head == nullptr)
    {
        cout << "Single Linked List is Empty" << endl;
    }
    else
    {
        Node* deleteNode = head;

        head = deleteNode->next;

        delete deleteNode;

        size--;
    }

}

---

✅ PushBack ( ) 함수 (뒤에 데이터 넣기)

• PushFront( )와는 다르게 PushBack은 head부터 순차적으로 뒤에 들어 가야하기 때문에 순회 포인터가 필요하다 (currentNode)

• 노드가 하나도 없을 때
  
  

• 기존 PushFront( )함수와 동일
  -> newnode 생성 후 head가 가리키게 하고 데이터 넣어주기

• 노드가 여러개 일때
  
  

• newnode를 생성하고, 순회포인터 currentNode 생성 후 head를 가리키게 함
  

• 반복문을 통해서 currentNode를 계속 이동시켜준 뒤 currentNode -> next가 nullptr인 곳에 도착함
  

• 그 위치에 newnode를 새노드를 넣고, 데이터 넣어주기
  

• 데이터가 들어왔으니 size ++

// 뒤에 값 넣기
void PushBack(T data)
{
    Node* newnode = new Node;

    // 노드가 하나도 없을때
    if (head == nullptr)
    {
        head = newnode;

        head->data = data;
        head->next = nullptr;
    }
    else
    {
        Node* currentNode = head;

        // 갱신 시켜주면서 이동(노드 끝자리 찾기)
        while (currentNode->next != nullptr)
        {
            currentNode = currentNode->next;
        }
        currentNode->next = newnode;
        newnode->data = data;
        newnode->next = nullptr;
    }
    size++;
}

---

✅ PopBack ( ) 함수 (뒤에 데이터 빼기)

• 노드가 하나도 없을 때
  
  

• PopFront( )함수와 동일하게 head == nullptr이면 노드가 하나도 없는 것. 즉, 뺄 데이터도 없다

• 노드가 하나일때
  
  
  

• deleteNode를 생성하고 head를 가리키게 한 뒤 deleteNode -> next를 nullptr로 가리키게 함
  

• 노드가 여러개일때
  
  

• 1. 삭제시키기 위한 deleteNode가 필요함
• 2. deleteNode가 가리키는 노드의 이전노드를 저장할 previousNode가 필요함
     -> 뒤에 데이터를 뺀 뒤 nullptr을 가리켜야 하는데 deleteNode의 이전노드의 정보를 알지 못하면, 이전노드가 해제된 메모리를 가리키는 현상이 발생함(댕글링포인터)

• 순회를 통해서 deleteNode -> next가 nullptr이 될때까지 이동
  

• previousNode는 deleteNode의 이전노드를 가리킴
  

• previousNode -> 를 nullptr로 이동시키기
  

• deleteNode를 해제하고 size --
  

// 뒤에 값 빼기
void PopBack()
{
    if (head == nullptr)
    {
        cout << "SingleLinkedList is Empty" << endl;
    }
    // 노드가 여러개 일때
    else
    {
        Node* deleteNode = head;
        Node* previousNode = nullptr;

        if (size == 1)
        {
            head = deleteNode->next;

            delete deleteNode;
        }

        else
        {
            while (deleteNode->next != nullptr)
            {
                previousNode = deleteNode;
                deleteNode = deleteNode->next;
            }

            previousNode->next = deleteNode->next;

            delete deleteNode;

        }
        size--;

    }
}

🔒 댕글링 포인터 : 해제된 메모리를 가리키는 현상

---

✅ 데이터를 보여주는 Show( )함수 & 노드의 크기 size & 소멸자

void Show()
{
    Node* currentNode;

    currentNode = head;

    while (currentNode != nullptr)
    {
        cout << currentNode->data << " ";

        currentNode = currentNode->next;
    }
}

// 사이즈 반환 ( & 사용하면 복사비용 줄어듬)
// 하나의 메모리 공간에 2개의 이름이 있다
int & Size()
{
    return size;
}

// 소멸자
~SingleLinkedList()
{
    while (head != nullptr)
    {
        // cout << "Delete" << endl;
        PopFront();
    }
}

📌 메인 함수

• template로 선언했기에 < > 안에 자료형을 지정해준다

int main()
{
    SingleLinkedList <int> singleLinkedList;

    singleLinkedList.PushFront(1);
    singleLinkedList.PushFront(2);
    singleLinkedList.PushFront(3);
    singleLinkedList.PushBack(4); // 3214


    singleLinkedList.PopBack(); // 4 지움

    singleLinkedList.PopFront(); // 3 지움


    singleLinkedList.Show();
}

결과값:

---

📌 단일 연결 리스트 장/단점

단일 연결 리스트의 장점

• 필요에 따라 크기가 동적으로 변화
• 데이터 삽입/삭제가 용이 -> 포인터만 수정하면 된다 (배열은 데이터 삽입/삭제 시 요소의 이동이 필요해서 연결리스트가 더 빠르다)

단일 연결 리스트의 단점

• head부터 순차적으로 접근해야하기 때문에, 맨 뒤의 데이터에 접근하기 위해서는 시간이 오래걸려 배열보다 비효율적이다 (최악의 경우, 시간복잡도 O(n)
• 각 노드마다 포인터를 저장해야 하기 때문에 추가적인 메모리 공간을 사용

단일 연결 리스트 시간복잡도

접근 O(n) / 탐색 O(n) / 삽입,삭제 O(1)

배열과 단일 연결 리스트 비교

배열

• 데이터 접근이 빠르다 (인덱스로 바로 접근)
• 삽입/삭제 시 요소들을 다 이동하여 비효율적이다

단일 연결 리스트

• 데이터 접근 시 순차적으로 접근한다(느리다)
• 삽입/ 삭제 시 포인터만 변경하여 효율적이다