[algorithm] 배열 / 연결리스트 / 스택 / 큐 / 덱

Array

일반적으로 배열은 메모리에 할당된 연속적인 공간을 차지함 

int arr[5] = {1,2,3,4,5}; 
//메모리에 연속적인 공간에 1,2,3,4,5를 할당함 
//컴퓨터는 배열의 첫번째 값의 메모리주소만을 기억함
//인덱스로 배열에 접근하면 컴퓨터는 첫번째 메모리주소로부터 인덱스만큼 떨어진 곳을 찾아 값을 가져옴
//그렇기 때문에 참조시 O(1)의 성능을 가짐 => 참조는 빠름

처음에 5만큼의 크기를 차지할 배열을 선언하고 이후 10만큼의 크기로 변경하려고 하면 
컴퓨터는 크기가 10인 연속적인 공간의 메모리를 다시 찾아야 하고, 값도 복사해서 다시 할당함 
+ 데이터 중간에 삽입하면 모든 데이터의 위치를 변경해야 하기 때문에 오버헤드 많이 발생
=> 일반적으로 배열은 데이터 추가 삭제에 있어서 O(n) (느림)

BUT 자바스크립트는 배열을 연속적인 메모리에 저장하지 않음
(불연속적인 메모리 공간에 저장된 값을 연결하여 사용자에게는 배열인 것처럼 보이게 함)

 

 

LinkedList

연결리스트의 각 요소는 불연속적인 메모리 공간에 저장되고 이를 연결하여 구현함
(초기에 크기를 선언할 필요없음)

연결리스트의 각 요소는 node라고 부름 
ㄴ> node는 data를 담는 변수와 다음 노드를 가리키는 next변수를 가진 구조로 되어있음

class Node{
  constructor(data, next = null){
    this.data = data;
    this.next = next;
  }
}

연결리스트의 가장 첫번째 node의 메모리 주소만 알고있다면 모든 노드에 접근 가능 
ㄴ> 첫번째 node를 head라고 부름
ㄴ> 연결리스트의 n번째 노드에 접근하고 싶다면, head의 next를 n번 실행해야함 => 데이터 참조시 O(n) (느림) -> 배열이 나음
ㄴ> 데이터 삽입삭제시에도 동일하게 O(n)(느림)-> but 배열보단 낫다 (연결리스트는 초기 크기를 지정하지 않기 때문에)

연결리스트의 마지막 노드는 null을 가리키며, 연결리스트가 비어있다면 head는 null을 참조함

자바스크립트의 이터러블이 떠오르는 연결리스트...! 

 

Stack

프링글스 통같은 구조 (First in Last out / Last in First Out) 후입선출
ㄴ> head(한쪽에서만)에서만 데이터가 들어오고 나감

 

Queue

먼저 온 사람이 먼저 나가는 구조 (First in First out) 선입선출
ㄴ> 운영체제의 작업 스케줄링에 사용함
ㄴ> 시작(front, head...)과 끝(rear, tail...)을 표시하는 두개의 포인터가 있음
ㄴ> head에서 데이터가 들어오고 tail에서 데이터가 나감

 

Deque

리스트의 양쪽모두에서 데이터 삽입과 삭제가 가능한 자료구조 
ㄴ> head에서 데이터가 들어오고 나가고, tail에서도 데이터가 들어오고 나감

덱에서는 head에 add, remove / tail에 add, remove를 구현하기 때문에
덱을 구현하면 stack과 queue도 구현 가능
(head의 add와 tail의 remove를 조합하여 stack을 만든다거나...)