7. STL : 더블링크드 리스트(Double Linked List)를 구현해보자.

 

더블 링크드 리스트

 

이중 연결 리스트는 하나의 노드에서 두 개의 링크를 갖게 되는데

선행 노드와 후속 노드에 주소를 각각의 링크에 연결시켜 양뱡향 겁색이 가능하게끔 하는 리스트이다.

단순 연결 리스트에서 삽입과 삭제를 위해서는 선행노드의 주소가 반드시 필요했던 것과 달리

이중 연결 리스트는 양방향 검색이 가능하기 때문에 삽입,삭제를 더 용이하게 진행할 수 있다.

실제로 이중 연결과 원형 연결을 같이 구현하여 이중 원형 리스트를 가장 많이 사용한다고 한다.

• node의 시작 pointer
• 리스트에 저장된 데이터의 개수
• Prev라는 포인터가 들어갔기에 일반적인 링크드 리스트보다 앞뒤를 순서를 더 고려해서 처리를 해줘야 함.

대략적인 구조

#include <iostream>

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

class DoublyLinkedList {
private:
    Node* head;
    Node* tail;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    ~DoublyLinkedList() {
        Node* current = head;
        Node* next;
        while (current) {
            next = current->next;
            delete current;
            current = next;
        }
    }

    void insert(int data) {
        Node* newNode = new Node{data, nullptr, nullptr};
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    void remove(int data) {
        Node* current = head;
        while (current && current->data != data) {
            current = current->next;
        }
        if (current) {
            if (current->prev) current->prev->next = current->next;
            if (current->next) current->next->prev = current->prev;
            if (current == head) head = current->next;
            if (current == tail) tail = current->prev;
            delete current;
        }
    }

    void display() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

기능

• 빈 리스트 만들기
• 리스트 없애기
• 데이터를 리스트에 추가하기
• 리스트에서 데이터를 삭제하기
• 리스트에서 데이터를 검색하기
• 리스트에 저장되어있는 데이터의 개수를 확인하기
• 리스트가 비어있는지 확인하기

리스트가 비어있는 경우 - Insert

struct node
{
	int data;
	node* prev;
	node* next;
	node(int item) : data(item), prev(nullptr), next(nullptr) {}

};

node* inNode = new node(33); //1
if (m_head == nullptr)  //2
{
	m_head = inNode;
}

리스트의 첫 번째 위치에 추가하는 경우

struct node
{
	int data;
	node* prev;
	node* next;
	node(int item) : data(item), prev(nullptr), next(nullptr) {}

};

node* inNode = new node(32); //1
if (pos == 0) // 제일 첫번쨰위치에 데이터를 추가하겠다.
{
	inNode->next = m_head; //inNode가 가리키는 next에는 1000노드(헤드)가 가리키는 값을 복사.
	m_head->prev = inNode; // 헤드가 가리키는 prev값에 inNode에 있는 2000이란 값을 복사
	m_head = inNode; // 해드는 32를 가리키도록 바꿈.
}

리스트 중간 위치에 추가하는 경우

struct node
{
	int data;
	node* prev;
	node* next;
	node(int item) : data(item), prev(nullptr), next(nullptr) {}

};
node* inNode = new node(20);
for (int i = 0; i < pos - 1; i++)
{
	curNode = curNode->next;
}

//insert a node at the last position
if (curNode->next == nullptr)
{
	inNode->prev = curNode;
	curNode->next = inNode;
}
else
{ //insert a node between nodes
	inNode->next = curNode->next;
	inNode->prev = curNode;
	curNode->next->prev = inNode;
	curNode->next = inNode;
}

삭제(Remove)

---

먼저 삭제할 노드의 링크를 모두 순차적으로 끊어준다(데이터 훼손 없이)

리스트의 첫번째 위치의 노드를 삭제하는 경우

if (pos == 0)
{
	delNode = m_head;
	m_head = m_head->next;
	m_head->prev = nullptr;
	delete delNode; // 동적할당이 되어 있으므로 삭제를 시켜줘야함.
}

리스트 중간 위치의 노드를 삭제하는 경우

node* delNode = m_head;
for (int i = 0; i < pos; i++)
{
	delNode = delNdelode->next;
}

//노드 마지막 위치 삭제
if (delNode->next == nullptr)
{
	delNode->prev->next = nullptr;
}

else// 중간에 있는 노드 삭제
{
	delNode->next->prev = delNode->prev;
	delNode->prev - .next = delNode->next;
}
delete delNode;

검색하기(데이터)

---

curNode = m_head;
for (int i = 0; i < pos; i++)
{
	curNode = curNode->next;
}
return curNode->data;

원형 링크드 리스트

원형 연결 리스트(circular linked list)

원형 연결 리스트는 마지막 노드의 링크가 첫번째 노드를 가리키는 리스트를 말한다. 그렇기 때문에 한 노드에서 다른 모든 노드로 접근이 가능하게 된다.

보통 헤드포인터가 마지막 노드를 가리키게 구성하여 리스트의 처음이나 마지막 삽입을 더 용이하게 만든다.

 

정리 : 배열 리스트 vs 링크드 리스트

• 공간
  • 배열은 정적이므로 최대크기를 미리 예상해야함.
  • 만들어 놓은 배열 공간이 실제로 쓰이지 않으면 나입
  • 연결 리스트는 실행시 필요에 따라 새로운 노드 생성.
  • 연결 리스트는 포인터 변수 공간을 요함.
• 검색 시간
  • 배열은 단번에 찾아감(묵시적 어드레싱 : 인덱스 연산)
  • 연결 리스트는 헤드부터 포인터를 따라감(현시적 어드레싱 : 포인터 읽기)
• 삽입, 삭제 시간
  • 배열의 삽입 : 오른쪽 밀림(Shift Right)
  • 배열의 삭제 : 왼쪽 밀림(Shift left)
  • 연결리스트 : 인접 노드의 포인터만 변경
• 그래서 어떨때 뭘쓰면 좋을까
  • 검색 위주라면 배열.
  • 삽입 삭제 위주라면 연결리스트
  • 최대 데이터 수가 예측이 불가능하다면 연결리스트.