본문 바로가기
Computer Science/Data Structures

[Data Structures] Linked List (연결 리스트)

by __K.Jun__ 2024. 7. 5.

Linked List

- 연속적인 메모리 위치에 저장되지 않고 포인터를 사용해서 연결되는 선형 데이터 구조

- 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함한다.

 

Linked List vs Array

- 배열은 비슷한 유형의 선형 데이터를 저장하는 데 사용할 수 있지만 다음과 같은 제한 사항이 있다.

- 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당 받아야 한다.

- 새로운 요소를 삽입하는 것은 비용이 많이 든다. (새로운 공간을 만들고, 기존 요소를 전부 이동시켜야 함)

 

Linked List의 장점

- 사이즈가 동적이다.

- 요소 삽입/삭제가 용이하다.

 

Linked List의 단점

- 요소에 대해 임의로 엑세스를 허용하지 않는다. -> 첫 번째 노드부터 순차적으로 요소에 엑세스 해야한다.

- 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요하다.

 

Singly Linked List

가장 간단한 형태의 Linked List이다. 노드가 한쪽 방향으로만 연결되어있다.

다음은 Singly Linked List의 ADT이다.

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

struct Node
{
    ElementType element;
    Position next;
};

List MakeEmptyList();
int isLast(Position, List l);
void Delete(ElementType x, List l);
Position FindPrevious(ElementType x, List l);
Position Find(ElementType x, List l);
void Insert(ElementType x, Position p, List l);
void DeleteList(List l);
void PrintList(List l);

 

다음은 Singly Linked List의 구현체이다.

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

List MakeEmptyList()
{
    List l = (List)malloc(sizeof(struct Node));
    l->element = -999;
    l->next = NULL;
    return l;
}

int isLast(Position p, List l)
{
    return p->next = NULL;
}

Position FindPrevious(ElementType x, List l)
{
    Position p;
    p = l;
    while (p->next != NULL && p->next->element != x)
    {
        p = p->next;
    }
    return p;
}

Position Find(ElementType x, List l)
{
    if (x == -1)
    {
        return l;
    }
    else
    {
        Position p;
        p = l->next;
        while (p != NULL && p->element != x)
        {
            p = p->next;
        }
        return p;
    }
}

void Insert(ElementType x, Position p, List l)
{
    if (p == NULL)
    {
        printf("Insertion(%d) Failed: cannot find the location to be inserted.\n", x);
    }
    else
    {
        Position tmp;
        tmp = (Position)malloc(sizeof(struct Node));

        tmp->element = x;
        tmp->next = p->next;
        p->next = tmp;
    }
}

void Delete(ElementType x, List l)
{
    Position p, tmp;
    p = FindPrevious(x, l);
    if (p->next == NULL)
    {
        printf("Deletion failed: element %d is not in the list\n", x);
    }
    else if (!isLast(p, l))
    {
        tmp = p->next;
        p->next = tmp->next;
        free(tmp);
    }
}

void PrintList(List l)
{
    PtrToNode tmp = NULL;
    tmp = l->next;
    if (tmp == NULL)
    {
        printf("list is empty!\n");
        return;
    }
    while (tmp != NULL)
    {
        printf("key: %d\t", tmp->element);
        tmp = tmp->next;
    }
    printf("\n");
}

void DeleteList(List l)
{
    Position p = NULL, tmp = NULL;
    p = l->next;
    l->next = NULL;
    while (p != NULL)
    {
        tmp = p->next;
        free(p);
        p = tmp;
    }
}

 

Doubly Linked List

노드가 다음 노드와 이전 노드를 가리키는 양방향 이중 연결 리스트이다.

다음은 Doubly Linked List의 ADT이다.

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

struct Node
{
    ElementType element;
    Position prev;
    Position next;
};

List MakeEmptyList();
int isLast(Position, List l);
void Delete(ElementType x, List l);
Position Find(ElementType x, List l);
void Insert(ElementType x, Position p, List l);
void DeleteList(List l);
void PrintList(List l);

 

다음은 Doubly Linked List의 구현체이다.

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

List MakeEmptyList()
{
    List l = (List)malloc(sizeof(struct Node));
    l->element = -999;
    l->prev = NULL;
    l->next = NULL;
    return l;
}

int isLast(Position p, List l)
{
    return p->next = NULL;
}

Position Find(ElementType x, List l)
{
    if (x == -1)
    {
        return l;
    }
    else
    {
        Position p;
        p = l->next;
        while (p != NULL && p->element != x)
        {
            p = p->next;
        }
        return p;
    }
}

void Insert(ElementType x, Position p, List l)
{
    if (p == NULL)
    {
        printf("Insertion(%d) Failed: cannot find the location to be inserted.\n", x);
    }
    else
    {
        Position tmp;
        tmp = (Position)malloc(sizeof(struct Node));

        tmp->element = x;
        tmp->next = p->next;
        if (p->next != NULL)
        {
            p->next->prev = tmp;
        }
        p->next = tmp;
        tmp->prev = p;
    }
}

void Delete(ElementType x, List l)
{
    Position p = Find(x, l);
    if (p == NULL || p == l)
    {
        printf("Deletion failed: element %d is not in the list\n", x);
        return;
    }

    if (isLast(p, l))
    {
        if (p->prev != NULL)
        {
            p->prev->next = NULL;
        }
    }
    else
    {
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    free(p);
}

void PrintList(List l)
{
    PtrToNode tmp = NULL;
    tmp = l->next;
    if (tmp == NULL)
    {
        printf("list is empty!\n");
        return;
    }
    while (tmp != NULL)
    {
        printf("key: %d\t", tmp->element);
        tmp = tmp->next;
    }
    printf("\n");
}

void DeleteList(List l)
{
    Position p = NULL, tmp = NULL;
    p = l->next;
    l->next = NULL;
    while (p != NULL)
    {
        tmp = p->next;
        free(p);
        p = tmp;
    }
}

 

Circularly Linked List

마지막 노드가 head 노드를 가리키는 원형 연결리스트이다.

다음은 Circularly Linked List의 ADT이다.

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

struct Node
{
    ElementType element;
    Position next;
};

List MakeEmptyList();
int isLast(Position p, List l);
void Delete(ElementType x, List l);
Position FindPrevious(ElementType x, List l);
Position Find(ElementType x, List l);
void Insert(ElementType x, Position p, List l);
void DeleteList(List l);
void PrintList(List l);

 

다음은 Circularly Linked List의 구현체이다.

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

List MakeEmptyList()
{
    List l = (List)malloc(sizeof(struct Node));
    l->element = -999;
    l->next = l;
    return l;
}

int isLast(Position p, List l)
{
    return p->next == l;
}

Position FindPrevious(ElementType x, List l)
{
    Position p;
    p = l;
    while (p->next != l && p->next->element != x)
    {
        p = p->next;
    }
    return p;
}

Position Find(ElementType x, List l)
{
    if (x == -1)
    {
        return l;
    }
    else
    {
        Position p = l->next;
        while (p != l && p->element != x)
        {
            p = p->next;
        }
        return p != l ? p : NULL;
    }
}

void Insert(ElementType x, Position p, List l)
{
    if (p == NULL)
    {
        printf("Insertion(%d) Failed: cannot find the location to be inserted.\n", x);
    }
    else
    {
        Position tmp;
        tmp = (Position)malloc(sizeof(struct Node));

        tmp->element = x;
        tmp->next = p->next;
        p->next = tmp;
    }
}

void Delete(ElementType x, List l)
{
    Position p, tmp;
    p = FindPrevious(x, l);
    if (isLast(p, l))
    {
        printf("Deletion failed: element %d is not in the list\n", x);
    }
    else
    {
        tmp = p->next;
        p->next = tmp->next;
        free(tmp);
    }
}

void PrintList(List l)
{
    PtrToNode tmp = l->next;
    if (tmp == l)
    {
        printf("list is empty!\n");
        return;
    }
    do
    {
        printf("key: %d\t", tmp->element);
        tmp = tmp->next;
    } while (tmp != l);
    printf("\n");
}

void DeleteList(List l)
{
    Position p = l->next;
    l->next = l;
    while (p != l)
    {
        Position tmp = p->next;
        free(p);
        p = tmp;
    }
}

 

Circular Doubly Linked List

말 그대로 원형 연결 리스트와 이중 연결 리스트가 혼합된 모양이다. tail 노드는 head 노드를 가리키고, head 노드는 tail 노드를 가리키는 형태가 형성된다.

다음은 Circular Doubly Linked List의 ADT이다.

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType;

struct Node
{
    ElementType element;
    Position prev;
    Position next;
};

List MakeEmptyList();
int isLast(Position p, List l);
void Delete(ElementType x, List l);
Position Find(ElementType x, List l);
void Insert(ElementType x, Position p, List l);
void DeleteList(List l);
void PrintList(List l);

 

다음은 Circular Doubly Linked List의 구현체이다.

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

List MakeEmptyList()
{
    List l = (List)malloc(sizeof(struct Node));
    l->element = -999;
    l->prev = l;
    l->next = l;
    return l;
}

int isLast(Position p, List l)
{
    return p->next == l;
}

Position Find(ElementType x, List l)
{
    if (x == -1)
    {
        return l;
    }
    else
    {
        Position p = l->next;
        while (p != l && p->element != x)
        {
            p = p->next;
        }
        return p != l ? p : NULL;
    }
}

void Insert(ElementType x, Position p, List l)
{
    if (p == NULL)
    {
        printf("Insertion(%d) Failed: cannot find the location to be inserted.\n", x);
    }
    else
    {
        Position tmp;
        tmp = (Position)malloc(sizeof(struct Node));

        tmp->element = x;
        tmp->next = p->next;
        if (p->next != NULL)
        {
            p->next->prev = tmp;
        }
        p->next = tmp;
        tmp->prev = p;
    }
}

void Delete(ElementType x, List l)
{
    Position p = Find(x, l);
    if (p == NULL || p == l)
    {
        printf("Deletion failed: element %d is not in the list\n", x);
        return;
    }

    if (isLast(p, l))
    {
        if (p->prev != NULL)
        {
            p->prev->next = NULL;
        }
    }
    else
    {
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    free(p);
}

void PrintList(List l)
{
    PtrToNode tmp = l->next;
    if (tmp == l)
    {
        printf("list is empty!\n");
        return;
    }
    do
    {
        printf("key: %d\t", tmp->element);
        tmp = tmp->next;
    } while (tmp != l);
    printf("\n");
}

void DeleteList(List l)
{
    Position p = l->next;
    l->next = l;
    while (p != l)
    {
        Position tmp = p->next;
        free(p);
        p = tmp;
    }
}

 

Linked List와 Array의  시간복잡도 차이

1) 데이터 탐색

- Linked List : 순차 접근 방식 -> O(N)

- Array : 인덱스 -> O(1)

 

2) 데이터 추가/삭제

- Linked List : 추가 하려는 데이터의 위치에 따라 다름. 맨 앞이라면 O(1), 맨 앞 그 이후라면 O(N)

- Array : 추가 하려는 데이터의 위치에에 따라 다름. 맨 뒤라면 O(1), 맨 뒤 그 이전이라면 O(N)

728x90

'Computer Science > Data Structures' 카테고리의 다른 글

[Data Structures] AVL Tree (AVL 트리)  (0) 2024.07.31
[Data Structrues] Binary Search Tree (이진 탐색 트리)  (0) 2024.07.20
[Data Structures] Tree (트리)  (0) 2024.07.15
[Data Structures] Stack and Queue (스택과 큐)  (0) 2024.07.11
[Data Structures] Array (배열)  (0) 2024.06.27

관련글

티스토리툴바