[JS] javaScript 기본 자료구조

01. 자료구조, Data Structure

프로그래밍에서 데이터를 구조적으로 표현하는 방식과, 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론이다.

배열

• Array
  • 배열은 가장 기본적인 데이터 구조이다.
  • 부여된 인덱스를 통해 원하는 데이터에 접근할 수 있고, 데이터를 효율적으로 검색하여 가져오는 게 가능하다.
  • 데이터를 추가, 삭제하는 과정이 비효율적이고 메모리의 낭비가 심하다.

연속 리스트

• Contiguous List
  • 배열처럼 연속적인 기억 장소에 데이터가 저장되는 자료구조이다.
  • 연속적으로 데이터가 저장되어 있어 검색에는 용이하지만, 데이터의 삽입이나 삭제는 용이하지 않다.

연결 리스트

• Linked List
  • 데이터를 임의의 기억공간에 기억시키되, 데이터 항목의 순서에 따라 노드의 포인터를 이용하여 서로 연결시킨 자료구조이다.
  • 새로운 데이터를 추가하고 삭제하는 것이 용이하고 효율적이다.
  • 배열처럼 메모리에 연속적으로 위치하지 않고 구조의 재구성이 필요없다.
  • 대용량 데이터 처리에 적합하지만, 연결이 끊어지면 다음 노드를 찾기가 어렵고 속도가 느리다는 단점이 있다.

스택

• Stack
  • 스택은 순서가 유지되는 선형 데이터 구조이다.
  • 리스트의 한쪽에서만 데이터의 삽입과 삭제가 일어나므로, 가장 마지막 요소부터 가장 처음 요소를 처리하는 LIFO(last in first out) 메커니즘을 갖고 있다.

큐 (Queue)

• Queue
  • 스택과 비슷하지만 먼저 입력된 요소를 먼저 처리하는 FIFO(fist in fist out) 메커니즘을 갖고 있다.
  • 리스트의 한쪽에서는 삽입이 일어나고, 다른 쪽에서는 삭제가 일어난다.
  • 데이터의 시작을 front, 끝 부분은 rear라고 한다.
  • 한 번에 하나의 데이터만 처리하는 단점이 있다.

그래프

• Graph
  • 정점(Vertex)와 간선(Edge)으로 이루어진 데이터 구조이다.
  • 방향 그래프와 무방향 그래프가 있다.
  • 데이터의 추가, 삭제가 용이하지만 데이터 간의 충돌이 일어날 수 있다.

트리

• Tree
  • 노드(node)로 구성된 계층적인 자료구조이다.
  • 최상위 노드(루트)를 만들고 그 아래에 자식을 추가하는 방식으로 트리구조는 다양하게 구현할 수 있다.
  • 노드와 노드를 잇는 선을 간선(edge)이라 한다.
  • 같은 부모 노드를 가지며 같은 레벨에 있는 노드를 형제(Siblings) 노드라 하고 자식이 없는 노드를 단말(Terminal) 노드라고 한다.