Data structure part.1 - Javascript

1. Stack

: 기본적으로 자바스크립트는 싱글 쓰레드(single thread) 기반 언어이므로, 호출 스택이 하나이다. 한번에 하나의 작업만 처리할 수 있다는 이야기이다.

호출 스택은 프로그램 상에서 현재 내가 어디에 있는지를 기록하는 자료구조이다.

현재 어떠한 함수를 실행하고 있다면, 해당하는 함수가 호출 스택의 가장 상단(top)에 위치하게 된다. 함수의 실행이 끝나게 되면 해당 함수는 호출 스택에서 제거된다. 결국 이 말은 마지막으로 스택에 들어간 것이, 가장 먼저 나오는 순서로 작동하다는 것이다(Last In, First Out).
서로 관계가 있는 여러 작업을 연달아 수행하며, 이전의 작업 내용을 저장해 둘 필요가 있을 떄 널리 사용

예시 코드를 보며 추가적으로 알아보자.

 

function sum(x, y) {
    return x + y;
}
function showDouble(x) {
    let y = sum(x, x);
    console.log(y);
}
showDouble(3);

 

맨 처음 해당 코드를 실행할 때에는 스택이 비어있다. 코드가 실행됨에 따라 스택이 변화하게 된다.

 

간단히 각 스택 프레임(Stack Frame)을 설명하자면,

1.비어있는 Call stack에서 새롭게 showDouble(3) 실행 (in)
2.showDouble 내부의 sum(x, x) 실행 후 out
3.순차적으로 console.log(y) 실행 후 out
4.마지막으로 showDouble(3) 실행 종료와 동시에 out
5.Call stack이 비워짐

 

만약 call stack이 최대 크기가 된다면?
=> "스택 날려버리기(overflowing)"가 일어난다.
브라우저에서 Uncaught RangerError: Maximum call stack size exceeded라는 에러 메시지를 띄워준다.

 

만약 call stack에 처리 시간이 오래 걸리는 함수가 있다면?
=> 이 떄에는 "동시성(Concurrency)"과 "이벤트 루프(Event Loop)" 개념이 필요하다.
single thread의 특성상, 한 번에 한가지 작업만 수행하므로, 긴 시간이 걸리는 함수 실행동안에 다른 것을 못하게 되는데,
이를 보완하고자 도입되는 개념이다. 비동기 콜백을 통하여 오래 걸리는 함수가 실행되는 동안 다른 작업을 수행할 수 있도록 한다.

 

 

작동 원리에 대해서 간단히 생각해본다면
어떠한 배열이 있다고 생각하고, 마지막으로 in 되는 것은 배열에 push하고, 마지막으로 in 되었던 것을 pop하는 방식으로 생각하면 될 것 같다.

1.배열의 생성
2.데이터를 in (배열에 push)
3.다른 데이터 추가적으로 in(배열에도 push)
4.데이터를 추출 out (배열로부터 pop)

5.마지막으로 추가되었던 자료가 뭔지 보기 (peek, return array[array.length-1] 같은 방식으로 가능할 듯)

 

 

2. Queue

-데이터를 넣을 수 있는 linear한 자료형
-stack과는 달리, First In First Out 규칙을 다름
-데이터를 집어넣는 enqueue, 추출하는 dequeue 등의 작업 가능
-순서대로 처리해야 하는 작업을 임시로 저장하는 Buffer로서 많이 사용

 

 

작동 원리에 대해서 간단히 생각해본다면
어떠한 배열이 있다고 생각하고, 마지막으로 in 되는 것을 배열에 push하고, 처음 in 되었던 것을 shift하는 방식으로 생각하면 될 것 같다.

1.배열의 생성
2.데이터를 in (배열에 push)
3.다른 데이터를 추가적으로 in (배열에 또 push)
4.데이터를 추출 out (배열로부터 shift)

5.가장 먼저 추가했던 자료가 뭔지 보기(peek, return array[0]으로 가능할 듯)

 

 

3. Linked list

list 자료구조는 자료를 나란히 저장하며, 중복된 데이터의 저장을 막지 않는다.
구현 방법에 따라서 크게 두 가지로 나뉜다.

1.선형 리스트(Lindear List) : 배열을 기반으로 구현된 리스트, 배열 리스트.
2.연결 리스트(Linked List) : 노드의 연결로 구현된 리스트

도식화된 자료가 필요하다면 다음의 주소로 가보자.
생활코딩 - Linked list.

 

1.배열 리스트(Array List)
: 가장 간단한 메모리 데이터 구조. 대부분의 프로그래밍 언어에서 배열은 기본으로 내장된 데이터 타입이다. 배열은 동일한 데이터 타입을 연속적으로 저장하는데, 당연히 자바스크립트에서는 타입이 다른 데이터들도 하나의 배열에 넣을 수 있다.
탐색 또는 정렬을 자주 하면 사용하자!

 

장점) 간단하여 사용 및 데이터 참조가 용이(index 값을 기준으로 어디든지 한 번에 참조가 되기 때문)
단점) 자바스크립트를 제외하고, 배열의 크기가 초기에 결정한대로 고정됨. 배열의 처음이나 중간에서 원소를 넣거나 빼려면 비싼 연산을 빈번히 수행하게 됨.

 

2.연결 리스트(Linked List)
:일련의 원소를 배열과 같이 차례대로 저장하지만, 원소들이 메모리상에 연속적으로 위치하지는 않는다.
추가/삭제가 많으면 사용하자!

 

-연속되는 항목들(node)이 pointer로 연결된다.
-마지막 항목은 null을 가리킨다.
-프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다.
-시스템 메모리가 허용하는 한도 내에서, 필요한만큼 길어질 수 있다.
-메모리 공간을 낭비하지 않는다.(pointer를 위한 추가 메모리를 필요로 하기는 하지만...)

장점) 배열에 비해 데이터의 추가/삽입 및 삭제가 용이
단점) 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없음. 탐색 속도가 떨어짐.

 

노드(Node)란?
: linked list에서 각 원소는, 원소 자신(data)과 다음 원소를 가리키는 pointer가 포함된 노드로 구성된다.

 

이 때에 Head라는 것은 연결이 시작되는 지점을 참조하는 것이다.

노드의 구조에 대해서 간략히 생각해본다면,

function Node(data) {
    this.data = data; // 해당 node가 가진 자료
    this.next = null; // 해당 노드가 가리키는 다음 노드를 가리킴
}

 

작동 원리에 대해서 간단히 생각해본다면
데이터를 담은 list라는 큰 틀의 class와 각각의 데이터를 담을 단일 원소인 node class 두 가지가 필요할 것이다.

 

1.LinkedList라는 함수 생성 및 실행
=> 함수 내부에서 LinkedList 클래스와 Node 클래스 각각을 생성한다.
=> LinkedList 클래스는 리스트의 길이 저장과 head를 개시해주는 역할을 한다.
=> Node 클래스는 각각의 노드가 가질 data와 다음 원소를 가리키는 pointer로 구성한다.

 

2.노드의 추가
(기존의 리스트가 A-B-C-D로 구성되어 있다고 가정, 추가될 노드는 X)

 

=> 리스트의 처음에 추가하는 경우라면,
새로운 노드의 추가는 새로운 Node의 인스턴스 생성하면서 함께 담고자 하는 value를 넣어주고, 새롭게 생성하는 노드를 head에 넣어준다.

 

=> 리스트의 중간에 추가하는 경우라면,
1)추가하고자 하는 자리의 index를 안다.(A와B 사이로 가정)
2)추가하고자 하는 자리 앞의 노드를 찾는다.(A)
3)찾은 노드의 next로서 추가할 노드로 지정한다.(A-X)
4)추가한 노드의 next로서 다음 노드를 지정한다.(A-X-B-C-D)

 

=> 데이터를 제거하는 경우라면,
1)예를 들어, 세번째 노드를 제거한다고 생각해보자.(C가 세번째 노드)
2)head, 두번째 노드, 세번째 노드 순서로 찾게 될 것이다.
4)두번째 노드의 next를 기존 네번째 노드로 변경한다.(A-B-D))
5)기존 세번째 노드를 제거한다.(C 제거)