[C++ / 자료구조]연결 리스트(Linked List)

연결리스트 참조 블로그

https://velog.io/@kon6443/Data-Structure-C-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-list

[Data Structure] C++ / 자료구조 / Linked list

 

 

해당블로그의 자료가 차후 도움이 될 듯하여 전체복사(타블로그 없어질경우 대비로)

Linked list

What to know

• 링크드 리스트란 배열과 비슷하게 선형적으로 연결된 자료구조이다.
• 하지만 인접한 메모리 공간에 저장되는 배열과 다르게 링크드 리스트는 인접한 메모리 공간에 저장되지 않는다.
• 위의 사진처럼 각 node마다 다음 node의 주소를 저장하고 있는 포인터가 있다.
  • 연결 리스트는 실제 메모리 공간에서 아무 규칙없이 저장되어진다.
  • 하지만 각 노드는 다음 노드의 주소값을 저장하고 있으므로 다음 노드의 값에 접근할 수 있다.
  • 각 노드는 데이터를 저장하는 변수와 다른 노드를 가르키는 포인터변수로 구성되어 있다.

• 대표적인 사용 예시
  • 인터넷 브라우저의 뒤로가기, 앞으로가기 기능.

연결 리스트를 사용하는 이유

• 배열의 사이즈는 고정되어 있고 배열을 선언할 때 배열의 사이즈를 항상 알아야 한다.
  • 배열에 할당된 메모리들은 사용 유무와 상관없이 항상 메모리를 차지한다.
• 링크드 리스트는 사이즈의 변동이 자유롭다.

index [] = [1, 2, 3, 4, 5]

• 예를들어, 2번째 요소 2를 지우는 경우가 생긴다면, 그 뒤에 있는 3,4,5모든 요소들을 한 칸씩 앞으로 당겨줘야 하고, 이 작업은 효율성이 좋지 못하다.
• 만약 index가 링크드 리스트로 만들어졌다면, 1다음에 3을 연결시켜 준 후 2를 지우면 된다.

연결 리스트의 단점

• 링크드 리스트는 Random access가 불가능하다.
  • 배열의 경우 index[1]라는 변수를 이용해 2에 바로 접근이 가능하지만 링크드 리스트는 맨 첫번째 노드부터 다음 노드를 반복해서 검색한다.
• 배열과 다르게 포인터 변수를 저장하므로 각 노드마다 추가적인 메모리 공간을 요구한다.

Singly Linked List (SLL)

• 단방향 연결 리스트의 첫번째 노드는 head라고 불린다.
  • head노드는 리스트가 비어있어도 항상 존재한다.
  • head로 정해진 노드는 data변수에 아무것도 저장하지 않는다.
  • 리스트가 비어있다면 head의 포인터 변수는 NULL을 향하고 있다.
• data변수의 data type은 무엇이든 될 수 있다.
• head를 포함한 모든 단방향 연결 리스트의 노드는 위 사진처럼 data를 저장하는 부분과 다음 노드의 주소값을 저장하는 포인터 변수로 구성되어진다.

• 아래는 CPP로 링크드 리스트를 구현한 간단한 예제이다.

// a linked list
#include <iostream>
using namespace std;

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

void printList(Node* head)
{
    Node* cursor = new Node();
    if(head == NULL) {
        cout<<"The head is NULL";
    } else {
        cursor = head->next;
        while(cursor != NULL) {
            cout<<cursor->data<<" ";
            cursor = cursor->next;
        }
    }
}

Node* insert(Node* head, int new_data)
{
    if (head == NULL) {
        cout << "The head is NULL";
        return head;
    }
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = head->next;
    head->next = new_node;
    return head;
}

Node* deleteNode(Node* head, int key)
{
    if (head == NULL) {
        cout << "The head is NULL";
        return head;
    }
    Node* cursor = new Node();
    cursor = head;
    while(cursor->next->data != key) {
        cursor = cursor->next;
    }
    Node* temp = new Node();
    temp = cursor->next;
    cursor->next = cursor->next->next;
    delete temp;
    return head;
}

int main()
{
    Node* head = new Node();
    head = insert(head, 1);
    head = insert(head, 2);
    head = insert(head, 3);
    printList(head);
    cout<<endl; 
    head = deleteNode(head, 1);
    printList(head);
    cout<<endl; 
    return 0;
}

# Result
3 2 1
3 2

Inserting a node

▼CPP로 구현한 새로운 노드를 삽입하는 함수 예제▼

void insertAfter(Node* prev_node, int new_data)
{
  
    // 1. Check if the given prev_node is NULL
    if (prev_node == NULL) {
        cout << "The given previous node cannot be NULL";
        return;
    }
  
    // 2. Allocate new node
    Node* new_node = new Node();
  
    // 3. Put in the data
    new_node->data = new_data;
  
    // 4. Make next of new node as
    // next of prev_node
    new_node->next = prev_node->next;
  
    // 5. move the next of prev_node
    // as new_node
    prev_node->next = new_node;
}

• 특정 노드의 다음노드 자리에 새로운 노드를 삽입할 수 있다.
• 위 사진의 tmp노드 다음은 원래 C노드지만, new->next=tmp->next;, tmp->next=new;를 사용해서 중간에 넣어줄 수 있다.
  • new->next=tmp->next;
    • 새로운 노드의 next포인터 변수의 주소값을 기존 tmp노드의 다음 노드 주소값으로 할당.
  • tmp->next=new;
    • tmp노드의 next포인터 변수의 주소값을 new노드 주소값으로 할당.

Deleting a node

▼CPP로 구현한 특정 노드를 지우는 함수 예제▼

Node* deleteNode(Node* head, int key)
{
    if (head == NULL) {
        cout << "The head is NULL";
        return head;
    }
    Node* cursor = new Node();
    cursor = head;
    while(cursor->next->data != key) {
        cursor = cursor->next;
    }
    Node* temp = new Node();
    temp = cursor->next;
    cursor->next = cursor->next->next;
    delete temp;
    return head;
}

Doubly Linked List (DLL)

• SLL은 head노드를 기본적으로 포함하지만 DLL은 head와 추가로 tail노드도 포함한다.
• tail또한 head와 마찬가지로 포인터값을 제외한 아무 데이터값을 할당받지 않는다.
• 양방향 연결 리스트의 노드는 두개의 포인터 변수 prev next와 data변수로 구성되어진다.

▼DLL의 기본 노드 구성▼

• head: DLL의 맨 앞 노드, 포인터값만 받는다(자료 저장X).
• tail: DLL의 맨 뒤 노드, 포인터값만 받는다(자료 저장X).

▼DLL의 기본 노드의 구성▼

• prev: 이전 노드의 주소값을 가지고 있다.
• next: 다음 노드의 주소값을 가지고 있다.
• data: 사용자가 원하는 data type의 변수로 지정.

Inserting a node

• 새로운 노드를 삽입하는 방법은 SLL 비슷하지만 DLL은 추가로 prev포인터만 신경써줄 필요가 있다.
• 노드 B와 C사이에 새로운 노드 E를 삽입하는 방법은 노드B를 prev로 지정해 준 후, prev의 다음노드를 E와 연결, E의 다음 노드를 C로 연결한다.
• 추가로 C의 이전 노드를 E로 연결, E의 이전 노드를 B로 연결한다.

▼CPP로 구현한 prev_node이후에 새로운 노드를 삽입하는 함수 예제▼

/* Given a node as prev_node, insert
a new node after the given node */
void insertAfter(Node* prev_node, int new_data)
{
	/*1. check if the given prev_node is NULL */
	if (prev_node == NULL)
	{
		cout<<"the given previous node cannot be NULL";
		return;
	}

	/* 2. allocate new node */
	Node* new_node = new Node();

	/* 3. put in the data */
	new_node->data = new_data;

	/* 4. Make next of new node as next of prev_node */
	new_node->next = prev_node->next;

	/* 5. Make the next of prev_node as new_node */
	prev_node->next = new_node;

	/* 6. Make prev_node as previous of new_node */
	new_node->prev = prev_node;

	/* 7. Change previous of new_node's next node */
	if (new_node->next != NULL) new_node->next->prev = new_node;
}

Deleting a node

• 위의 이미지에서 노드의 순서대로 A B C라고 가정한 후 B노드를 지우는 방법.
  • A노드의 다음 노드를 C로 할당.
  • C노드의 이전 노드를 A로 할당.
  • B노드 삭제.

// C++ program to delete a node from
// Doubly Linked List
#include <bits/stdc++.h>
using namespace std;

/* a node of the doubly linked list */
class Node
{
	public:
	int data;
	Node* next;
	Node* prev;
};

/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
void deleteNode(Node** head_ref, Node* del)
{
	/* base case */
	if (*head_ref == NULL || del == NULL)
		return;

	/* If node to be deleted is head node */
	if (*head_ref == del)
		*head_ref = del->next;

	/* Change next only if node to be
	deleted is NOT the last node */
	if (del->next != NULL)
		del->next->prev = del->prev;

	/* Change prev only if node to be
	deleted is NOT the first node */
	if (del->prev != NULL)
		del->prev->next = del->next;

	/* Finally, free the memory occupied by del*/
	free(del);
	return;
}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the
beginning of the Doubly Linked List */
void push(Node** head_ref, int new_data)
{
	/* allocate node */
	Node* new_node = new Node();

	/* put in the data */
	new_node->data = new_data;

	/* since we are adding at the beginning,
	prev is always NULL */
	new_node->prev = NULL;

	/* link the old list off the new node */
	new_node->next = (*head_ref);

	/* change prev of head node to new node */
	if ((*head_ref) != NULL)
		(*head_ref)->prev = new_node;

	/* move the head to point to the new node */
	(*head_ref) = new_node;
}

/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked list */
void printList(Node* node)
{
	while (node != NULL)
	{
		cout << node->data << " ";
		node = node->next;
	}
}

/* Driver code*/
int main()
{
	/* Start with the empty list */
	Node* head = NULL;

	/* Let us create the doubly linked list 10<->8<->4<->2 */
	push(&head, 2);
	push(&head, 4);
	push(&head, 8);
	push(&head, 10);

	cout << "Original Linked list ";
	printList(head);

	/* delete nodes from the doubly linked list */
	deleteNode(&head, head); /*delete first node*/
	deleteNode(&head, head->next); /*delete middle node*/
	deleteNode(&head, head->next); /*delete last node*/

	/* Modified linked list will be NULL<-8->NULL */
	cout << "\nModified Linked list ";
	printList(head);

	return 0;
}

클래스로 만든 DLL

#include <iostream>

using namespace std;

class Node {
    friend class DLL;
private:
    int data;
    Node* pNext;
    Node* pPrev;
public:
    Node();
    Node(int data);
    ~Node();
};

class DLL {
private: 
    Node* pHead;
    Node* pTail;
    Node* pCursor;
public:
    DLL();
    ~DLL();
    void insertion(int);
    void deletion(int);
    void traversal();
    void reverseTraversal();
    int size();
};

Node::Node() {
    this->pPrev = NULL;
    this->pNext = NULL;
}

Node::Node(int data) {
    this->data = data;
    this->pPrev = NULL;
    this->pNext = NULL;
}

Node::~Node() {}

DLL::DLL() {
    pHead = new Node(); 
    pTail = new Node();
    pCursor = new Node();
    pHead->pNext = pTail;
    pTail->pPrev = pHead;
}

DLL::~DLL() {}

void DLL::insertion(int data) {
    Node* temp = new Node(data);
    pCursor = pHead->pNext;
    pHead->pNext = temp;
    temp->pNext = pCursor;
    pCursor->pPrev = temp;
    temp->pPrev = pHead;
}

void DLL::deletion(int data) {
    if(pHead->pNext == pTail) cout<<"No node exists"<<endl;
    else {
        pCursor = pHead->pNext;
        while(pCursor != pTail) {
            if(pCursor->data == data) {
                pCursor->pPrev->pNext = pCursor->pNext;
                pCursor->pNext->pPrev = pCursor->pPrev;
                delete pCursor;
                return ;
            } else {
                pCursor = pCursor->pNext;
            }
        }
    }
}

void DLL::traversal() {
    if(pHead->pNext == pTail) cout<<"No node exists"<<endl;
    else {
        pCursor = pHead->pNext;
        while(pCursor != pTail) {
            cout<<pCursor->data<<" ";
            pCursor = pCursor->pNext;
        }
        cout<<endl;
    }
}

void DLL::reverseTraversal() {
    if(pTail->pPrev == pHead) cout<<"No node exists"<<endl;
    else {
        pCursor = pTail->pPrev;
        while(pCursor != pHead) {
            cout<<pCursor->data<<" ";
            pCursor = pCursor->pPrev;
        }
        cout<<endl;
    }
}

int DLL::size() {
    int size = 0;
    if(pHead->pNext == pTail) return size;
    else {
        pCursor = pHead->pNext;
        while(pCursor != pTail) {
            size++;
            pCursor = pCursor->pNext;
        }
        return size;
    }
}

int main() {

    DLL dll;
    dll.insertion(1);
    dll.insertion(2);
    dll.insertion(3);
    dll.traversal();
    dll.reverseTraversal();
    cout<<"After deletion"<<endl;
    dll.deletion(3);
    dll.traversal();
    dll.reverseTraversal();
    cout<<"size: "<<dll.size()<<endl;

    return 0;
}