순차적 자료구조 : Sequential data structure

1. 배열, 리스트

index로 임의의 원소를 접근
-연산자 [] a[2]:-1
-삽입 append, insert
-삭제 pop, remove

여기서 단순히 연산, append, pop의 경우는 O(1) 이지만, insert나 remove의 경우 자리를 줄이고 옮기고 해야 하기에 O(n)이 소요된다.

2. Stack, Queue, Dequeue

제한된 접근(삽입, 삭제)도 허용

1. stack : LIFO(last in first out)
   가장 마지막에 들어간 것이 처음으로 나온다. push하면 맨 아래부터 차근차근 쌓이고 삭제될 때는 맨 위의 값 부터 삭제된다.

2. queue : FIFO(first in first out)
   stack과 반대로 먼저 들어온 순서대로 먼저 나간다.

3. dequeue : stack + queue
   들어갈 때도 위에서 or 아래서 들어갈 수 있고, 나갈 때도 위 or 아래서 나갈 수 있다.

3. Linked list (연결 리스트)

연속된 공간이 아니라 독립적으로 저장되어 있다.
그렇기에 이 공간에서 순서를 연결해 주어 순서를 표기한다.

여기서는 이렇게 독립적으로 저장되어 있기에 인덱스로 접근할 수 없다.
맨 처음부터 3->2->-1로 따라가야 한다.

https://www.youtube.com/watch?v=buJBlTsWlW0&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=7