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

Onam Kwon·2022년 7월 1일

Data Structure

목록 보기

1/4

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;
}

References

https://www.geeksforgeeks.org/data-structures/linked-list/

https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-doubly-linked-list/?ref=lbp

Geeksforgeeks copyright information

https://www.geeksforgeeks.org/copyright-information/

Onam Kwon

권오남 / Onam Kwon

다음 포스트

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

Data Structure

Linked list

What to know

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

연결 리스트의 단점

Singly Linked List (SLL)

Inserting a node

Deleting a node

Doubly Linked List (DLL)

Inserting a node

Deleting a node

클래스로 만든 DLL

References

Geeksforgeeks copyright information

[Data Structure] 자료구조 / C++ / 스택 / 큐

0개의 댓글