[알고리즘/자료구조] 링크드 리스트

링크드 리스트 ( Linked List)

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

기본 형태

링크드 리스트가 연결된 형태.

첫 번째 노드를 Head라 하고 마지막 노드를 tail이라고 합니다.

C 언어로 구조체 정의.

typedef struct tagNode
{
    int Data;  // Data Field
    struct tagNode* NextNode   //Node Pointer
}Node;
 
Node MyNode;

더블 링크드 리스트 (Doubly Linked List) 구조

typedef struct tagNode
{
    int Data;  // Data Field
    struct tagNode* PrevNode   //Node Pointer
    struct tagNode* NextNode   //Node Pointer
}Node;
 

-노드 추가

-노드 삽입

- 노드 삭제

- 관련 간단한 코드

/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 11 - 08
/*
*/
 
 
#include <stdio.h>
#include <iostream>
#include <conio.h>
 
using namespace std;
 
typedef struct LinkedNode
{
    int data;
    struct LinkedNode* p_nextNode;
} Node;
 
Node* Create_Node(int data)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
 
    NewNode->data = data;  
    NewNode->p_nextNode = NULL; 
 
    return NewNode;
}
 
void Destroy_Node(Node* Node)
{
    free(Node);
}
 
void Insert_Node(Node** Head, Node* NewNode)
{
    
    if ( (*Head) == NULL ) 
    {        
        *Head = NewNode;
    } 
    else
    {
        Node* Tail = (*Head);
        while ( Tail->p_nextNode != NULL )
        {
            Tail = Tail->p_nextNode;
        }
 
        Tail->p_nextNode = NewNode;
    }
}
 
void InsertAfter_Node(Node* p_currentNode, Node* NewNode)
{
    NewNode->p_nextNode = p_currentNode->p_nextNode;
    p_currentNode->p_nextNode = NewNode;
}
 
 
void Remove_Node(Node** Head, Node* Remove)
{
    if ( *Head == Remove )
    {
        *Head = Remove->p_nextNode;
    }
    else
    {
        Node* p_currentNode = *Head;
        while ( p_currentNode != NULL && p_currentNode->p_nextNode != Remove )
        {
            p_currentNode = p_currentNode->p_nextNode;
        }
 
        if ( p_currentNode != NULL )
            p_currentNode->p_nextNode = Remove->p_nextNode;
    }
}
 
void Search_Node(Node* Head)
{
    int i = 0;
    Node* p_currentNode = Head;
 
    while ( p_currentNode != NULL)
    {
        i++;
        cout << " Linked List " << i << " data Value is    :  " << p_currentNode -> data << endl;
        p_currentNode = p_currentNode->p_nextNode;
    }
}
 
int Get_NodeCount(Node* Head)
{
    int n_Count = 0;
    Node* p_currentNode = Head;
 
    while ( p_currentNode != NULL )
    {
        p_currentNode = p_currentNode->p_nextNode;
        n_Count++;
    }
 
    return n_Count;
}
 
Node* Get_NodeIndex(Node* Head, int index)
{
    Node* p_currentNode = Head;
 
    while ( p_currentNode != NULL && (--index) >= 0)
    {
        p_currentNode = p_currentNode->p_nextNode;
    }
 
    return p_currentNode;
}
 
void main( void )
{
    int n_Count = 0;
    Node* L = NULL;
    Node* current_node = NULL;
    Node* NewNode = NULL;
 
    NewNode = Create_Node(15);
    Insert_Node(&L, NewNode);
 
    NewNode = Create_Node(63);
    Insert_Node(&L, NewNode);
 
    NewNode = Create_Node(96);
    Insert_Node(&L, NewNode);
 
    NewNode = Create_Node(8);
    Insert_Node(&L, NewNode);
 
    NewNode = Create_Node(-57);
    Insert_Node(&L, NewNode);
 
    NewNode = Create_Node(-2);
    Insert_Node(&L, NewNode);
 
    n_Count = Get_NodeCount(L);
 
    Search_Node(L);
 
    current_node = Get_NodeIndex(L, 2);
    NewNode = Create_Node(79);
    InsertAfter_Node(current_node, NewNode);
 
    current_node = Get_NodeIndex(L, 5);
    Remove_Node(&L, current_node);
 
    cout << endl << "============================================" << endl << endl;
 
    Search_Node(L);
 
    getch();
}
 

출처 : 위키피디아, 위키백과

https://en.wikipedia.org/wiki/Linked_list