Javascript 자료구조

<단순 구조(Primitive Data Structure)>

• 프로그래밍에서 사용되는 기본 데이터 타입
• JS의 원시 타입에는 string, number, bollean, null, undefined 가 있다.

<비단순 구조(Non-Primitive Data Structure)>

• 여러 데이터를 목적에 맞게 효과적으로 저장하는 자료 구조
• JS의 참조 타입에는 object, array, function 이 있다.

<선형 구조(Linear Data Structure)>

• 저장된 자료의 전후 관계가 1:1 인 경우

<비선형 구조(Non-Linear Data Structure)>

• 데이터 항목 사이의 관계가 1:n 인 경우

 

---

 

<스택(Stack) / 큐(Queue)>

• 스택과 큐 모두 Linear한 자료 구조형이다. 이 둘은 아주 유사한 자료구조이지만, element가 제거되는 방식에 차이가 있다.
• 스택과 큐는 자바스크립트에 내장되어 있지 않음으로, 사용을 원하면 스스로 구조를 만들어야 한다.

 

<스택(Stack)>

• 스택은 흔히 아는 자바스크립트 엔진에서의 콜 스택이 제거되는 방식과 동일하다.
• 마지막으로 삽입된 element가 가장 먼저 제거되는 방식을 취한다.
• LIFO (Last In, First Out) 구조를 가진다.
• 따라서, 스택은 브라우저 히스토리(이전 페이지, 다음 페이지) 또는 ctrl+z로 이전 작업을 취소하는 등의 동작에 쓰이는 자료구조이다.
•  구조를 만들 때 배열(array)과 연결 리스트(linked list) 모두 크게 상관은 없다.

    const stack = [];

    // push 값을 스택에 할당한다.

    stack.push(1);

    stack.push(2);

    stack.push(3);

    console.log(stack); // [1, 2, 3]



    stack[stack.length-1]; // peek : 3 - 마지막에 삽입된 값

    stack.pop(); // [1, 2]

    stack.pop(); // [1]

    stack.pop(); // []

    // 삽입순서와 반대순서로 값을 뺀다.

 

<큐(Queue)>

• 큐는 먼저 들어가면 먼저 나가는 개념이다.
• FIFO (First In, First Out) 구조를 가진다.
• 식당 예약, 티켓 예매와 같은 큐(Queue)를 자료구조로 사용할 것이다.
• 구조를 만들 때는 배열(array)로 만들면 좋지 않다. (element 제거 후 index 재조정 때문)
• 따라서, Queue는 반드시 연결 리스트(Linked List)로 만든다.

    const queue = [];

    queue.push(1);

    queue.push(2);

    queue.push(3);

    console.log(queue); // [1, 2, 3]



    queue.shift(); // [2, 3]

    queue.shift(); // [3]

    queue.shift(); // []

    // 삽입순서와 같은 순서로 값을 뺀다.

 

<배열(Array)>

• 배열은 대부분의 프로그래밍 언어에서, 가장 간단하고 가장 많이 쓰이는 자료 구조형이다.
• 자료들이 메모리 주소(선반)에 순서대로 차곡차곡 정렬되어 있기 때문에 특정 데이터를 순차적으로 반복(iterate) 해야 하는 경우 배열은 최상의 자료 구조형이다.

<연결 리스트(Linked List)>

• 연결 리스트(Linked List)는 여러개의 노드로 이루어져 있다.
• 각각의 노드는 데이터와 다음 노드가 무엇인지 알려주는 주소를 가지고 있다.
• 연결 리스트(Linked List)는 새로운 데이터를 추가하거나, 데이터의 위치를 찾거나, 제거하는 기능이 있어야 한다.

 

<배열(array) / 연결 리스트(Linked List)의 장단점>

- 배열(array)

1) 각 element(값)들이 서로 연관되어 있어 속도가 빠르다. (장점)

2) 메모리 공간이 한정되어 있기 때문에 할당된 메모리를 다 사용하면 현재 배열을 다른 곳에 복사하기 때문에

   메모리를 더 사용하게 될 수도 있다. (단점)

 

- Linked List

1) 메모리가 사방팔방 흩어져있어 속도가 array 비하여 상대적으로 느릴 수 있다. (단점)

2) 메모리 공간이 한정되어 있지 않기 때문에 얼마든지 계속 값을 추가 가능하다. (장점)

---

<Map>

• ES6 부터는 Map 자료구조가 추가 되어 편리하게 사용가능하다.
• Map은 키가 있는 데이터를 저장한다는 점에서 객체와 유사하다.
• Map은 키에 다양한 자료형을 허용한다는 점에서 차이가 있다.

const map = new Map();
// set으로 Map 객체에 삽입
map.set("t1", 1); // {"t1" => 1}  -> key : "t1", value : 1
map.set("t2", 2); // {"t1" => 1, "t2" => 2}  -> key : "t1", value : 1

map.set(1, "num"); // 숫자형 키
map.set(true, "bool"); // 불린형 키

// get으로 Map 객체 조회
map.get("p1"); // 1
map.get("p2"); // 2
map.get(1); // "num"
map.get(true); // "bool"

// delete로 Map 객체 삭제
map.delete("p1"); // 삭제가 성공하면 true를 반환

// clear로 맵 안의 프로퍼티 전부 삭제
map.clear();

 

<Set>

• Map과 비슷하지만, 중복된 값을 허용하지 않는다.
• Set은 키가 없는 값이 저장 된다.
• ES6 기준 문법

내용 준비중