7일차

이중 연결 리스트

∙ 연결 리스트 종류

- 단순 연결 리스트

> 다음 노드에 대한 링크만 가지고 있는 연결 리스트 

> 한쪽 방향으로만 순회가 가능 (단방향 연결 리스트)

 

- 이중 연결 리스트 

> 이전 노드와 다음 노드에 대한 링크를 가지고 있는 연결 리스트

> 양방향 순회가 가능 (양방향 연결 리스트)

 

- 원형 연결 리스트 

> 일반적인 연결 리스트의 마지막 노드 링크가 처음 노드를 가리키도록 구성된 자료 구조

> 처음 노드가 다시 나타나면 순회를 멈춤

 

 

∙ 이중 연결 리스트의 구조

- 노드 구조체

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

- 이중 연결 리스트 클래스

class DoublyLinkedList
{
	//맴버 변수
	private:
    	int count;
        Node* header;
        Node* trailer;
    
    //구현한 곳
    public:
    	DoublyLinkedList();
        ~DoublyLinkedList();
        
        void insert(Node* p, int vall);
        void erase(Node* p);
        
        void print_all(); //정방향 출력
        void print_reverse(); //역방향 출력
};

 

- 이중 연결 리스트 생성

DoublyLinkedList()
{
	count = 0;
    
    //dummy node들을 0으로 초기화 하고, prev, next 값을 NULL로 초기화
    header = new Node {0, NULL, NULL};
    trailer = new Node {0, NULL, NULL};
    
    //header의 next가 trailer의 prev를 가리킴
    header -> next = trailer;
    //trailer의 prevrk headerdml next를 가리킴
    trailer -> prev = header;

 

- 이중 연결 리스트에 원소 삽입

void insert(Node* p, int val)
{	
	//새로운 node를 생성, 첫번째 인자는 data, 두 번째 인자는 prev, 세 번째 인자는 next이다.
	Node* new_node = new Node {val, p->prev,p};
    
    //새로운 노드의 prev노드의 next값을 new_node를 가리키게 한다.
    new_node -> prev -> next = new_node;
    
    //새로운 노드의 next노드의 prev값을 new_node를 가리키게 한다.
    new_node -> next -> prev = new_node;
    
    //node가 새로 추가 되었다는 기록
    count++;
}

 

- 이중 연결 리스트에서 노드 삭제하기

void erase(Node* p)
{
	//p의 prev가 가리키는 node에서 p의 next가 가리키는 위치로 수정
	p -> prev -> next = p -> next;

	//p의 next가 가리키는 node에서 p의 preve가 가리키는 위치로 수정
    p -> next -> prev = p -> prev;
    
    //p을 삭제(메모리 삭제)
    delete p;
    
    count--;

 

- 이중 연결 리스트 전체 데이터 출력하기

//정방향으로 데이터 출력
void print_all()
{
	// 현재 위치의 포인터를 curr변수에 넣는다.
	Node* curr = header -> next;
    
    while (curr != trailer) {
    	cout << curr -> data << ", ";
        curr -> curr -> next;
       }
   cout << endl;
}


//역순으로 데이터 출력
void print_reverse()
{
	Node* curr = trailer -> prev;
    
    while (curr != header){
    	cout << curr -> data << ", ";
        curr -> curr -> prev;
    }
    cout << endl;
}

 

- 전체 소스 코드

#include <iostream>

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

class DoublyLinkedList
{
private:
	int count;
	Node* header;
	Node* trailer;

public:
	DoublyLinkedList()
	{
		count = 0;
		header = new Node {0, NULL, NULL};
		trailer = new Node {0, NULL, NULL};
		header->next = trailer;
		trailer->prev = header;
	}

	~DoublyLinkedList()
	{
		while (!empty()) {
			pop_front();
		}

		delete header;
		delete trailer;
	}

	// 노드 p 앞에 val 값을 갖는 새로운 노드를 삽입
	void insert(Node* p, int val)
	{
		Node* new_node = new Node {val, p->prev, p};
		new_node->prev->next = new_node;
		new_node->next->prev = new_node;
		count++;
	}

	void push_front(int val)
	{
		insert(header->next, val);
	}

	void push_back(int val)
	{
		insert(trailer, val);
	}

	// 노드 p를 삭제
	void erase(Node* p)
	{
		p->prev->next = p->next;
		p->next->prev = p->prev;
		delete p;
		count--;
	}

	void pop_front()
	{
		if (!empty())
			erase(header->next);
	}

	void pop_back()
	{
		if (!empty())
			erase(trailer->prev);
	}

	bool empty() const
	{
		return count == 0;
	}

	int size() const
	{
		return count;
	}

	void print_all() const
	{
		Node* curr = header->next;

		while (curr != trailer) {
			std::cout << curr->data << ", ";
			curr = curr->next;
		}

		std::cout << std::endl;
	}

	void print_reverse() const
	{
		Node* curr = trailer->prev;

		while (curr != header) {
			std::cout << curr->data << ", ";
			curr = curr->prev;
		}

		std::cout << std::endl;
	}
};

int main()
{
	DoublyLinkedList ll;
	ll.push_back(10);
	ll.push_back(20);
	ll.push_back(30);
	ll.print_all();
	ll.print_reverse();

	// ll: header -> 10 -> 20 -> 30 -> trailer

	ll.pop_front();
	ll.pop_back();
	ll.print_all();

	ll.push_front(100);
	ll.push_back(400);
	ll.print_all();
}

 

∙ 이중 연결 리스트의 장단점

- (단순 연결 리스트 대비) 이중 연결 리스트의 장점

> 링크가 양방향이므로 양방향 검색이 가능

 

- (단순 연결 리스트 대비) 이중 연결 리스트의 단점

> 이전 노드링크를 위한 여분의 공간 사용

> 데이터의 삽입과 삭제 구현이 더 복잡