Data-Structure - Linked Lists

Sequential Representation은 연속적인 노드들의 데이터가 고정된 거리만큼 떨어져서 존재함을 의미합니다. 하지만 임의 데이터의 Insertion(삽입)과 deletion(삭제)가 매우 비용 효율적이지 못한 작업이 됩니다. 즉 삽입과 삭제에 과도한 행동이 필요하다는 것입니다.

 

하지만 Linked Representation은 메모리의 어디든지 분포할 수가 있습니다. 또한 ordered list와 달리 안의 데이터들이 모두 다 같은 타입일 필요가 없습니다. Linked Representation은 data fields와 다음 노드를 가리킬 link or pointer fields를 가집니다. 이는 Sequential Representation과 다르게 임의의 데이이터의 삽입과 삭제가 매우 빠릅니다.

 

위와 같은 형태를 띄기 때문입니다.

 

데이터의 삽입

 

Linked list에서의 삽입의 과정은

• 현재 사용하지 않는 노드를 만듭니다
• 데이터 필드를 GAT로 만듭니다
• GAT노드를 FAT가 가리키는 HAT를 가리키게 합니다.
• 또한 FAT노드를 GAT노드를 가지고 있는 a를 가리키게 하면 됩니다.

데이터의 삭제

Linked list에서 데이터의 삭제 과정은

• GAT를 직접적으로 가리키는 원소를 찾습니다.
• 찾은 워소의 link field를 GAT가 가리키는 노드로 설정합니다.

위와 같이 삽입에는 MALLOC을 삭제에는 free를 꼭 해주어야 합니다.

 

이를 이제 c언어 코드로 구현한 것은 아래와 같습니다.

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

#define ERROR_KEY -100

#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

#define REALLOC(p, s)                           \
    if (!((p) = realloc(p, s)))                 \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

typedef struct listNode_
{
    int data;
    struct listNode_ *link;
} listNode, *listPointer;

/* create a linked list with two nodes */
listPointer create2()
{
    listPointer first, second;
    MALLOC(first, sizeof(*first));
    MALLOC(second, sizeof(*second));

    second->link = NULL;
    second->data = 20;

    first->data = 10;
    first->link = second;

    return first;
}

/* insert a new node with data = 50 into the chain first after node x */
void insert(listPointer *first, listPointer x, int data)
{
    listPointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->data = data;
    // 만약 first가 null이 아니라면
    if (*first)
    {
        temp->link = x->link;
        x->link = temp;
    }
    else
    // 만약 first가 null이라면
    {
        temp->link = NULL;
        *first = temp;
    }
}

/* delete x from the list, trail is the preceding node and *first is the front of the list */
void delete (listPointer *first, listPointer trail, listPointer x)
{
    if (trail)
        trail->link = x->link;
    else
        *first = (*first)->link;

    free(x);
}

void printList(listPointer first)
{
    printf("The list contains: ");
    for (; first; first = first->link)
        printf("%4d", first->data);

    printf("\n");
}

int main(void)
{
    listPointer first = NULL;
    insert(&first, first, 10);
    insert(&first, first, 30);
    insert(&first, first->link, 20);

    delete (&first, first->link, first->link->link);
    delete (&first, NULL, first);

    printList(first);

    return 0;
}

위와 같이 제가 원하는 결과가 나옴을 볼 수 있습니다.

 

Linked Stacks and Queues

또한 저희는 Linked-List를 활용하여 Stack과 Queu를 구현할 수 있습니다. Linked Stacks는 쉽게 stack의 top에서 노드를 추가하고 더할 수 있습니다. 그 다음으로는 Linked Queues는 쉽게 rear에서 노드를 추가할 수 있고 front에서 쉽게 노드를 제거할 수 있습니다.

 

linked-stack

 

다음 위 그림과 같이 표현할 수 있습니다.

 

Linked Stacks

이를 간단히 c언어 코드로 작성한 것은 아래와 같습니다.

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

#define MAX_STACKS 10 /* maximum number of stacks */
#define ERROR_STATE -100

#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

#define REALLOC(p, s)                           \
    if (!((p) = realloc(p, s)))                 \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

typedef struct
{
    int key;
} element;

typedef struct stack_
{
    element data;
    struct stack_ *link;
} stack, *stackPointer;

stackPointer top[MAX_STACKS];

element stackEmpty()
{
    element errElement;
    errElement.key = ERROR_STATE;
    printf("\nstack is empty!!");
    return errElement;
}

/* add item to the ith stack */
void push(int i, element item)
{
    // make temp stackPointer
    stackPointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->data = item;
    temp->link = top[i];
    top[i] = temp;
}

/* remove top element from the ith stack */
element pop(int i)
{
    stackPointer temp = top[i];
    element item;
    if (!temp)
        return stackEmpty();
    item = temp->data;
    top[i] = temp->link;
    free(temp);
    return item;
}

void popAndPrint(int i)
{
    int key = pop(i).key;
    if (key == ERROR_STATE)
        return;
    printf("%d ", key);
}

int main(void)
{
    element newElement = {1};
    push(0, newElement);
    newElement.key = 3;
    push(0, newElement);
    newElement.key = 2;
    push(0, newElement);

    popAndPrint(0);
    popAndPrint(0);
    popAndPrint(0);
    popAndPrint(0);

    return 0;
}

top[0]에서만 진행된 stack LIFO정책이 정상 작동하는 것을 확인할 수 있습니다.

이를 간단히 그림으로 표현하자면 아래와 같습니다.

linked-stack 기본 구조

linked-stack의 add동작 구조

linked-stack pop동작 과정

 

linked-stack 총 정리

Multiple Queues

또한 Linked-list로 queue를 구현할 수 있는데, 생각보다 간단해서 너무 놀랐다.

기본적인 구조는 multiple stack과 비슷한데 뒤에 rear가 queue의 맨 뒤의 원소를 가리키고 있다는 점에서 다릅니다.

이는 구현하기 전에 먼저 multiple queues의 add와 delete의 동작원리에 대해서 살펴보고 코드를 짜보겠습니다.

multiple-queues의 add가 동작하는 원리

multiple-queues의 delete가 동작하는 원리

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

#define MAX_QUEUES 10 /* maximum number of stacks */
#define ERROR_KEY -100

#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

#define REALLOC(p, s)                           \
    if (!((p) = realloc(p, s)))                 \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }
typedef struct
{
    int key;
} element;

typedef struct queue_
{
    element data;
    struct queue_ *link;
} queue, *queuePointer;

queuePointer front[MAX_QUEUES], rear[MAX_QUEUES];

int capacity = 1;

element queueEmpty()
{
    element errorElement;
    errorElement.key = ERROR_KEY;
    fprintf(stderr, "queue is empty, cannot delete element\n");
    return errorElement;
}

void addq(int i, element item)
{
    /*
        add item to the rear of queue i
    */
    queuePointer temp;
    MALLOC(temp, sizeof(*temp));

    temp->data = item;
    temp->link = NULL;

    if (front[i])
    {
        rear[i]->link = temp;
    }
    else
    {
        front[i] = temp;
    }
    rear[i] = temp;
}

element deleteq(int i)
{
    /*
        delete an element from queue i
     */
    queuePointer temp = front[i];
    element item;
    if (!temp)
    {
        return queueEmpty();
    }
    item = temp->data;
    front[i] = temp->link;
    free(temp);
    return item;
}

int main(void)
{
    element newElement = {1};
    addq(0, newElement);
    newElement.key = 3;
    addq(0, newElement);
    newElement.key = 2;
    addq(0, newElement);

    printf("%d ", deleteq(0).key);
    printf("%d ", deleteq(0).key);
    printf("%d ", deleteq(0).key);
    printf("%d ", deleteq(0).key);
}

아주 기초적인 코드를 c언어로 구현하였습니다. 또한 결과는 아래와 같습니다.

queue의 FIFO정책에 따라 잘 작동하는 것을 볼 수 있습니다.

multiple-queues총 정리