자료구조) 연결리스트

📌 개요

• 연결리스트란?
• 연결리스트의 장/단점
• 연결리스트의 종류
• 구현

🤔 연결리스트란?

연결리스트란 각 노드가 데이터와 포인터를 가지고
한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다.

노드?

노드는 연결리스트의 기본 단위가 되는 것으로써 두 가지로 구성됩니다.

• 데이터: 데이터를 담습니다.
• 링크: 이전 혹은 다음 노드를 가리키는 포인터입니다.

✔ 연결리스트의 장/단점

장점

연결리스트는 길이가 가변적일 수 있다는 것이 가장 큰 장점입니다.
배열은 유한한 길이를 설정해줘야 하지만, 연결리스트는 포인터로 연결하기만 하면 되니까요.

단점

하지만 포인터로 연결해줬기에, 배열처럼 인덱스로 접근이 불가합니다.
특정 값을 읽으려면 연결리스트의 처음부터 포인터로 다가가야 하기에, O(n)의 시간이 걸립니다.

💡 연결리스트의 종류

연결리스트는 다음 4가지 종류의 복합으로 이루어져 있습니다.

• 단일 연결 리스트 (Singly Linked List)
• 이중 연결 리스트 (Doubly Linked List)
• 원형 연결 리스트 (Circularly Linked List)
• 헤더 & 트레일러 연결 리스트 (Header & Trailer Linked List)

단일 연결 리스트

• 가장 단순한 연결 데이터 구조
  

이중 연결 리스트

• 노드가 링크 2개(prev, next)로 구성되어 있습니다.
  

원형 연결 리스트

• 마지막 노드의 링크가 헤드 노드의 주소입니다.
  

헤더 & 트레일러 연결리스트

• 헤더 노드와 트레일러 노드를 추가하여 편의성을 높일 수 있습니다.
• 값이 없어도
  

💻 구현

헤더가 트레일러가 있는 이중 연결 리스트를 구현해보았습니다.

#include <stdio.h>
#include <stdlib.h>

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

Node* head; 
Node* tail; 
int count; 

Node* makenode(int data);
void create();
void add(int position, int data);
void delete(int position);
void read(int position);
void print();

Node* makenode(int data)
{
    Node *node = (Node*)malloc(sizeof(Node));
    node->prev = NULL;
    node->data = data;
    node->next = NULL;

    return node;    
}

void create()
{
    head = (Node*)malloc(sizeof(Node));
    tail = (Node*)malloc(sizeof(Node));
    head->data = NULL;
    tail->data = NULL;

    head->next = tail;
    head->prev = head; 
    tail->next = tail;
    tail->prev = head;    
}

void add(int position, int data)
{
    if (position - 1 > count)
    {
        printf("invalid position\n");
        return;
    }

    Node* new = makenode(data);
    Node* n;
    n = head;

    for (int i = 0; i < position - 1; i++)
        n = n->next;
    
    new->prev = n;
    new->next = n->next;
    n->next->prev = new; 
    n->next = new;

    count++;

}

void delete(int position)
{
    if (position > count)
    {
        printf("invalid position\n");
        return;
    }

    Node* n;
    n = head;

    for (int i = 0; i < position; i++)
        n = n->next;
    
    n->prev->next = n->next;
    n->next->prev = n->prev;
    n->next = NULL;
    n->prev = NULL;

    count--;
}

void read(int position)
{
    if (position > count)
    {
        printf("invalid position\n");
        return;
    }

    Node* n;
    n = head;
    
    for (int i = 0; i < position; i++)
        n = n->next;

    printf("%d\n", n->data);
}

void print()
{
    Node* n;
    n = head;

    while (n->next != tail)
    {
        n = n->next;
        printf("%d", n->data);
        
    }
    printf("\n");
}