Data Structure: Stack, Queue, Linked list

1. Stack

 

Stack of plates by Robert Therrien

 

 스택이란 Last In First Out(LIFO) 규칙에 따라 동작하는 동적인 데이터 구조를 가리킨다. 다시 말해 스택에서는 가장 늦게 추가된 자료가 가장 먼저 나간다. 비유하자면, 스택은 위에 첨부된 미술 작품의 사진처럼 여러 개의 접시를 쌓아 놓은 것 같은 형태와 비슷하다. 새 접시가 하나 필요하다면, 접시 더미 맨 위에 쌓여 있는 접시 한 장을 꺼내어 쓰면 된다. 그 접시는 아마 아주 아주 높은 확률로, 여러 접시들 가운데 가장 최근에 더미 위에 올려진 접시일 것이다. 굳이 무거운 접시들을 들어, 그 아래에 새 접시를 넣는 것보다는 접시 더미 위에 새 접시를 쌓는 게 훨씬 더 간단하니까! 

 

 스택에서 자료를 추가하고 제거하는 데에는 규칙이 있다. 첫째로, 스택 구조의 가장 위쪽에서만 자료의 추가/제거가 일어난다. 가장 상단부에 있는 자료를 top element라고 한다. 둘째로, 한 번에 하나의 자료만 추가/제거할 수 있다. 통상적으로 스택에서 자료를 추가하는 것은 push, 제거하는 것은 pop이라 부른다.

 

 

 스택을 그림으로 나타내면 다음과 같다.

 스택의 크기는 element가 얼마나 쌓였는지, 즉 top element를 기준으로 파악한다.

 

 스택의 push, pop을 간단한 의사코드로 나타내보았다:

1. 자료가 쌓일 컨테이너(스택)를 선언해 준다.
2. 스택의 사이즈를 나타내 줄 변수(top)를 선언해 준다. 이 때 스택에는 데이터가 없으므로 top의 값은 0이다. 

<push>
1. input 데이터를 스택에 쌓는다. 이 데이터가 top element가 된다.
2. 스택의 사이즈인 top이 1 커진다.

<pop>
1. top element, 즉 가장 마지막으로 넣어준 데이터를 꺼내온다.
2. 스택 사이즈인 top이 1 작아진다.
3. 만약 top이 0일 경우, 즉 스택에 자료가 없는 경우 pop을 실행해도 동작하지 않도록 한다.

2. Queue

 

photo by Melanie Pongratz, 출처: unsplash.com

 

 큐는 First In First Out(FIFO) 구조로 자료를 저장하는 형식이다. 큐는 단어 뜻 그대로 대기줄과 비슷한 구조라고 이해하면 된다. 인기 맛집에서 식사를 하기 위해 웨이팅을 하고 있다고 가정해 보자. 줄에 빨리 설수록 빨리 식당에 들어갈 수 있다. 마찬가지로, 큐에서도 가장 먼저 추가된 자료가 가장 먼저 나간다. 

 

 큐에서는 가장 앞 쪽(front) 부터 자료가 꺼내지게(dequeue)되고, 뒤(rear)에서부터 새로운 자료가 추가(enqueue)된다. 

 

 큐를 그림으로 나타내면 다음과 같다.

 

 큐의 크기는 front에서 rear를 뺀 만큼이 될 것이다. 

 

 큐의 enqueue, dequeue, 그리고 사이즈를 출력하는 함수 size를 의사코드로 표현해보자:

1. 자료를 넣을 컨테이너(큐)를 선언해 준다.
2. 큐의 가장 앞(front)과 끝(rear)를 나타내는 변수를 선언한다.

<enqueue>
1. input 데이터를 받아 큐에 넣어준다.
2. 데이터가 하나 들어왔으므로, rear에 1을 더한다. 

<dequeue>
1. 큐의 제일 앞에 있는 데이터를 꺼내온다.
2. 앞에 있는 데이터가 큐에서 빠졌으므로, front에서 1을 뺀다.
3. 만일 큐에 데이터가 없는 경우, 즉 front와 rear의 값이 같은 경우 dequeue를 실행해도 동작하지 않도록 한다.

<size>
1. rear에서 front를 뺀 값을 출력한다.

 

3. Linked List

 링크드 리스트는 엘리먼트의 집합을 저장하는 방법으로, 링크드 리스트 내의 각 엘리먼트들은 노드(Node)의 형태로 저장되어 있다. 하나의 노드는 데이터 파트(data part), 넥스트 파트(next part)라는 두 부분으로 이루어져 있다. 데이터 파트에는 엘리먼트가 저장이 되어 있고, 넥스트 파트는 다음 노드를 가리키고 연결하는 역할을 한다. 때문에 넥스트 파트를 포인터(pointer)라 부르기도 한다.

 

 여러 개의 노드가 연결이 되어, 마치 사슬과 같은 형태를 이룰 때 링크드 리스트가 생성된다. 링크드 리스트의 첫 번째 노드는 헤드(Head) 또는 퍼스트(First)라고 불린다. 헤드는 링크드 리스트를 사용하기 위한 기준점으로서, 비유적으로는 대문과도 같은 역할을 한다. 마지막 노드는 null을 가리킨다. 

 

 링크드 리스트를 그림으로 나타내면 다음과 같다.

 

 

링크드 리스트에 대해 공부하며 나에게 가장 신선했던 부분은 엘리먼트를 삭제하는 방식이었다. '링크'라는 이름에서 유추할 수 있듯 링크드 리스트의 핵심은 관계다. 리스트에서 삭제하고자 하는 엘리먼트가 생기면 해당 엘리먼트와 다른 엘리먼트 간의 관계를 끊으면 된다. 다시 말해 삭제하고자 하는 엘리먼트를 가리키던 포인터가, 그 엘리먼트의 다음 엘리먼트를 가리키는 형태로 수정을 해 주면 된다. 도식화시켜 표현하면 다음과 같다.

 

세 개의 노드가 연결되어 있는 링크드 리스트가 있다고 해 보자. 가운데에 있는 노드를 삭제하고자 한다. 이때 우리가 할 일은 가장 오른쪽에 있는 노드의 포인터(현재는 가운데 노드를 가리키고 있음)가 가장 왼쪽에 있는 노드를 가리키도록 수정하는 하는 것이다.

 

 

여기서, 나머지 노드들과의 '링크'를 잃은 가운데 노드는 어떻게 될까? 이 때 가비지 컬렉션(garbage collector)이라는 메커니즘이 작동한다. 덕분에 사용자가 자료를 별도로 삭제하는 처리를 거치지 않아도, 가운데 노드는 가비지 컬렉터에 의해 수거되게 된다. 

 

 

링크드 리스트의 끝에 노드를 추가하는 addToTail, 헤드의 노드를 지우는 removeHead, 특정 자료가 링크드 리스트 내에 포함되어 있는지를 확인하는 contains 메소드를 의사코드로 표현해 보았다.

 

1. head와 tail을 프로퍼티로 갖는 링크드 리스트를 만들어 준다.
2. data와 pointer를 프로퍼티로 갖는 노드를 만든다. 

<addToTail> : 새로운 데이터를 받아 링크드 리스트에 추가하는 함수.
1. 링크드 리스트에 자료가 하나도 없는 경우, 
1-1. 링크드 리스트의 head에 새로운 노드를 할당해 준다.
1-2. 이 때 링크드 리스트에 노드는 단 하나 뿐이므로, 이 노드는 링크드 리스트의 가장 처음이자 끝이기도 하다. 따라서 tail에 같은 노드를 할당해 준다.
2. 링크드 리스트에 이미 자료가 들어와 있는 경우,
2-1. 기존 링크드 리스트의 tail의 pointer가 새로운 노드를 가리키도록 한다.
2-2. 기존 tail은 이제 링크드 리스트의 마지막 노드가 아니므로, 새로운 노드가 새로운 tail이 되어야 한다. 

<removeHead>: 링크드 리스트의 head를 제거하는 함수. 제거한 head에 담겨 있던 데이터를 return한다.
1. 링크드 리스트에 자료가 하나도 없는 경우,
1-1. head는 비어있으므로 함수가 작동하지 않는다.
2. 링크드 리스트에 이미 자료가 들어와 있으나, 하나뿐인 경우. 
2-1. 링크드 리스트의 head에 있던 자료를 리턴한다.
2-2. 링크드 리스트의 head와 tail를 비운다.
3. 링크드 리스트에 2개 이상의 자료가 들어와 있는 경우.
3-1. 링크드 리스트의 head에 있던 자료를 리턴한다.
3-2. 링크드 리스트의 새로운 head를, 기존 head의 다음 노드로 재할당한다. 즉 기존 head의 pointer가 가리키던 노드가 새로운 head가 된다.

<contains>: 어떠한 데이터를 받아, 그 데이터가 링크드 리스트에 포함되어 있는지를 판단하는 함수.
1. 링크드 리스트에 자료가 하나도 없는 경우,
1-1. false를 리턴한다.
2. 링크드 리스트에 자료가 들어와 있는 경우,
2-1. head node를 시작으로 각 노드의 data 프로퍼티를 살핀다.
2-2. 링크드 리스트의 끝에 다다를 때까지, 즉 노드의 pointer가 null을 가리킬 때까지 탐색을 한다.
2-2. 자료를 찾은 경우 true를 리턴, 그렇지 않은 경우 false를 리턴한다.