Linked Lists란 무엇인가?

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

 

학과 수업시간에 배운 내용을 그때그때 정리하고자 한다.

시험에도 도움이 되고 나중에 이후 무언가를 준비할때도 도움이 될듯하다

(절대 시험을 너무 망쳐서 강제로 복습하는게 아니다)

 

 

Linked Lists

 

Linked list 의 가장 큰 특징은 pointer를 통해서 다음 요소를 access할 수 있다는 것이며 

각 element 를 node라고 부른다.

 

출처: programiz

위 그림에서 파란색 상자 하나가 node인것이다. 

 

위 구조에서 보듯이 next가 또다른 같은 구조의 node를 가리키고 있기 때문에

recursive하다는 특징을 가지고 있다. 

 

코드로 구현하면 아래와 같다.

typedef struct linked_node list;

struct linked_node {
	int data;
        list* next;
};

위 코드에서 *이 무엇인지 모른다면 pointer 에 대해 공부하고 오면 좋다.

 

Linked list의 끝을 명확히 하기 위해서 우리는2가지 방법을 사용하는데

1. NULL pointer를 사용하며 이것을 NULL-terminated list라고 부른다. 

끝의 짧아지는 세로선이 NULL을 의미한다.

2. Dummy node를 가리키도록 한다. 

dummy node는 우리가 linked list의 끝을 알기 위한 일종의 신호일뿐 우리가 신경쓰지 않아도 되는 node이며 이후 dummy node를 가진 linked lists로 설명을 이어나갈 예정이다.

빨간색 node가 dummy node이다.

 

Linked Lists에서 segment

Linked lists에서 시작은 첫 node가 있는 곳이며 끝은 마지막 노드의 next가 가리키는 주소값이 된다. 

위의 경우에서는 end가 dummy node의 주소값이 되는것이다. 

 

Linked lists에서 segments를 뽑을 때 시작하는  node는 포함이고 end node는 포함되지 않는다. 수학적 수식으로 나타내면

[start, end)라고 볼 수있다. 

 

주어진 start node와 end node가 제대로 된 segment를 형성하는지에 대한 함수를 구현해보자

 

bool yes_segment(list* start, list*end)
{
  list* l = start;
  while (l !=NULL) { # pointer이기 때문에 NULL을 dereference할 수 없다.
     if (l==end) return true; #empty segment
     l = l-> next; # end에 도달하지 않았다면 다음 node로 넘어간다.
    }
    return false;
 }

Linked list에서 element 지우고 더하기

Linked lists의 구조상 2가지 경우로 element를 지울 수 있다. 

1) 시작 node에 있는 element를 지우고 싶을 때

-start node의 element를 잡아서 return하고 start를 새롭게 포인트한다.

-O(1) 의 시간 복잡도를 가진다.

int x= start->data;
start = start->next;
return x;

2) 마지막 node의 element를 지우고 싶을 때

- start부터 end 전 node까지 가면서 end를 바꾸고 해당 element를 return 한다.

-O(n)의 시간 복잡도를 가진다.

list* l = start;
while (l->next != end) l = l->next;
end = l;
return l->data;

element를 추가하고 싶을 때도 마찬가지이다.

1) 시작 node 전에 element를 추가하고 싶을 때

- 추가하기 위한 새로운 empty node를 생성하고 value를 넣고 start를 재설정한다.

-O(1)의 시간복잡도를 가진다

list* l = alloc(list);
l-> data = new;
l-> next = start;
start = l; # 새로운 node가 start

2) end node로 element를 추가하고 싶을 때

-기존의 dummy node에 추가하고픈 element를 넣고 end의 next를 새로운 dummy node로 설정

-O(1)의 시간복잡도를 가진다.

end->data = x;
end->next = alloc(list); # 새로운 dummy node
end = end->next;

Linked lists를 Queues로

Queue도 linked list의 구조로 되어있다고 생각해보자

그렇다면 queue의 front는 linked list의 start이고 back은 end node일 것이다. 

=> double linked list가 된다. 

 

code로 표현할때 queues는 queue*라는 타입을 가진 value가 되며 이에 따라 NULL이 될 수 없다. 

그림으로 나타내면 아래와 같다.

그림실력이 매우 허접하다..

이 구조에 따라 enqueue/dequeue도 모두 가능하다.

void enqueue(queue* Q, int x) #add at the back
//@requires is_queue(Q);
//@ensures is_queue(Q);
//@ensures !queue_empty(Q);
{
    Q->back->data = x;
    Q->back->next = alloc(list);
    Q->back = Q->back->next;
}

int deq(queue* Q) # remove from the front
//@requires is_queue(Q);
//@ensures is_queue(Q);
//@ensures !queue_empty(Q);
{
    int x = Q->front->data;
    Q->front = Q->front->next;
    return x;
}

해당 queue가 empty queue인지 아닌지 판단하는 함수와 새로운 empty queue를 만들수도 있다.

bool empty_queue(queue* Q)
//@requires is_queue(Q);
{
   return Q->front == Q->back;
}

queue* queue_new()
//@ensures is_queue(\result);
//@ensures queue_empty(\result);
{
    queue*Q = alloc(queue);
    Q->front = alloc(list);
    Q->back = Q->front;
    return Q;
}

Stack as linked lists

Stack의 관점에서 보아도 마찬가지이다. 

stack의 top이 segment의 start가 되고 stack의 floor가 segment의 end가 된다. 

 

stack의 top에 element를 push하는것도, top의 element를 pop하는것도, empty stack을 체크하는 것도, 새로운 empty stack을 만드는것도 모두 가능하다.

 

void push(stack* S, int x)
//@requires is_stack(S);
//@ensures is_stack(S);
//@ensures !stack_empty(S):
{
    list*L  = alloc(list);
    L->data =x;
    L->next = S->top;
    S->top = L;
}

int pop(stack* S)
//@requires is_stack(S);
//@requires !stack_empty(S);
//@ensures is_stack(S);
{
    int x = S->top->data;
    S->top = S->top->next;
    return x;
}

bool empty_stack(stack* S)
//@requires is_stack(S);
{
   return S->top == S->floor;
}

stack* stack_new()
//@ensures is_stack(\result);
//@ensures empty_stack(\result);
{
   stack*S = alloc(stack);
   S->top = alloc(list);
   S->floor=S->top;
   return S;
}

위 코드들에서의 공통점은 stack에서 floor가 거의 사용되지 안는다는 점이다. 

따라서 우리는 floor를 지우고 마지막 노드가 NULL을 가리키게 하며 NULL-terminated lists를 만든다.

이에 따라 empty stack을 체크하는 함수와 새로운 stack을 만드는 함수가 아래와 변형될 수 있다. 

bool empty_stack(stack* S)
//@requires is_stack(S);
{
   return S->top == NULL; # floor가 없어지고 NULL로 끝나기 때문에
}

stack* stack_new()
//@ensures is_stack(\result);
//@ensures empty_stack(\result);
{
   stack*S = alloc(stack);
   S->top = NULL;
   return S;
}

Sharing in Linked Lists

만약 우리가 기존 stack을 update하고 그것을 새로운 stack으로 지정한다면 그걸 어떻게 나타낼 수 있을까?

code로는 생각보다 쉽게 구현할 수 있다. 

기존 S라는 stack에 14를 push한다고 해보자.

 

stack_t t = push(S, 14);

그림으로 나타낸다면 아래와 같을 것이다.

그림에서 보는것과 같이 우리는 두개의 stack이 list suffix를 share하고 있음을 알 수 있다.