연결리스트

연결된 노드를 표현해주는 자료구조.

각 노드는 이전 노드와 다음 노드를 가리킨다.

장점은 시작이나 끝 지점에 아이템을 추가, 삭제 시 O(1)에 가능함.

다만 특정 인덱스는 상수 시간에 접근할 수 없음(시작이나 끝 지점부터 타고타고 넘어가야 함.)

--

양방향 예제

#include <cstdio>
struct node
{
    node *prev;
    node *next;
    int data;
}; 
 
void init();
void insert(char com, int num);
void elimination(char com, int num);
void see();
node *head, *foot;
 
int main()
{
    char command;
    int comnum;
    init();
    while (1)
    {
        printf("입력 - i / 삭제 - d\n : ");
        scanf("%c", &command);
        if (command == 'i')
        {
            printf("앞 삽입 - f / 뒷 삽입 - e\n : ");
            while (getchar() != '\n');
            scanf("%c", &command);
            printf("몇 번째 위치?\n : ");
            scanf("%d", &comnum);
            insert(command, comnum);
        }
        else if (command == 'd')
        {
            printf("앞 삭제 - f / 뒷 삭제 - e\n : ");
            while (getchar() != '\n');
            scanf("%c", &command);
            printf("몇 번째 위치?\n : ");
            scanf("%d", &comnum);
            elimination(command, comnum);
        }
        while (getchar() != '\n');
    }
}
void init()
{
    head = new node;
    foot = new node;
    head->prev = head;
    head->next = foot;
    foot->prev = head;
    foot->next = foot;
    head->data = -1;
    foot->data = -1;
}
void insert(char com, int num)
{
    if (com != 'f' && com != 'e' && num < 1)
        printf("잘못된 명령입니다.\n");
    int newdata;
    node *now, *newnode = new node;
    printf("입력하실 값은?(자연수&int범위)\n : ");
    scanf("%d", &newdata);
    if (com == 'f')
    {
        now = head;
        while (num--)
            now = now->next;
        newnode->next = now;
        newnode->prev = now->prev;
        now->prev->next = newnode;
        now->prev = newnode;
        newnode->data = newdata;
    }
    else if (com == 'e')
    {
        now = foot;
        while (num--)
            now = now->prev;
        newnode->prev = now;
        newnode->next = now->next;
        now->next->prev = newnode;
        now->next = newnode;
        newnode->data = newdata;
    }
    see();
}
void elimination(char com, int num)
{
    if (com != 'f' && com != 'e' && num < 1)
        printf("잘못된 명령입니다.\n");
    node *now;
    if (com == 'f')
    {
        now = head;
        while (num--)
            now = now->next;
        now->next->prev = now->prev;
        now->prev->next = now->next;
        delete now;
    }
    else if (com == 'e')
    {
        now = foot;
        while (num--)
            now = now->prev;
        now->next->prev = now->prev;
        now->prev->next = now->next;
        delete now;
    }
    see();
}
void see()
{
    node *a = head->next;
    while (a->data != -1)
    {
        printf("%d   ", a->data);
        a = a->next;
    }
    printf("\n");
}