1. Deque

Deque의 정의

Deque는 Double Ended Queue의 양방향 대기열이라고도 불리는 자료구조이다.

Deque의 구조

Deque는 Stack의 특성과 Queue의 특성이 혼합되어 있다.
Deque는 양방향이 열려있는 구조로, Queue와 외형적으로 비슷한 구조이다. 그러나 Deque는 LIFO, FIFO와 같은 순서에 구속되지 않는다.

Deque의 특징

1. Stack및 Queue를 모두 사용할 수 있다.
   Deque는 양쪽으로 데이터를 추가하고 삭제할 수 있어서 Stack과 Queue를 구현할 수 있다.
2. 양방향 끝에서 데이터 추가, 삭제가 용이하다.
3. 양방향 끝이 아닌 임의의 데이터만 추가하거나 삭제하는 건 불가능하다.
   Deque는 양방향 끝의 인덱스 정보를 가지고 있다. 양방향의 데이터가 아닌 중간에 있는 데이터에 접근하려고 할 때, 양쪽 끝 이외의 인덱스 정보가 없어서 접근할 수 없다.

2. Linked List

Linked List의 정의

선형으로 그룹화된 데이터의 집합으로 데이터와 다음 데이터의 주소를 포함하고 있는 하나의 노드가 선형으로 연결된 자료구조

Linked List의 구조

Linked List는 배열과 같이 선형으로 이루어진 자료구조이다.
연속된 공간이 아니라 흩어져 있는 공간에 노드들의 연결로 이루어진 자료구조이다. 하나의 노드에는 데이터와 다음 노드의 주소가 담겨있다. 그리고 각 노드는 다음 노드를 가르킨다. 연속된 메모리 주소가 아니기 때문에 직접 주솟값을 가지고 있어야 다음 노드로 접근할 수 있다. 마지막 노드는 다음을 가리킬 곳이 없으므로 새로 추가되기 전까지는 null을 가리킨다.

메모리에 표시한 Linked List와 배열

Linked List의 특징

1. 노드의 추가와 삭제가 빠르고 쉽다.
   배열은 메모리 순서가 정해져 있어서 값을 추가하거나 삭제할 때 메모리에 재할당을 해야 하지만 Linked List는 순서가 지정되지 않은 특성 때문에 데이터를 담은 노드를 어디에도 손쉽게 추가하거나 삭제할 수 있다.
2. 노드의 값을 찾으려면 최대 전체를 순회해야 한다.
   Linked List의 노드는 메모리에 흩어져 있어서 특정 노드로 쉽게 접근할 수 없다.
   Linked List의 첫 번재 노드를 head node라고 한다 .순회하기 전까지는 head node의 정보만 알고 있다. 필요한 값이 있는지 확인하려면 head node에 연결된 다음 노드로 접근해야 하고, 접근한 노드에 원하는 값이 없다면 다시 다음 노드로 이동해야 한다.
   head node에 있는 값은 O(1)의 시간 복잡도를 가지지만, 마지막 요소의 값에 접근하기 위해서는 요소의 개수만큼 순회해야 하기 때문에 최악의 경우로 O(n)의 시간 복잡도를 가진다.

Linked List 실사용 예제

• 삽입과 삭제가 중요한 곳에 활용
  splice, join, split method처럼 데이터 삽입 삭제가 중요한 메소드의 구현에도 활용할 수 있다.
• 동적 기억장소 관리(dynamic storage management)
  실행되는 작업에 필요한 크기만큼의 메모리를 할당하는 방법에 활용된다.
• Garbage collection
  참조자료형의 데이터 타입을 관리하는 알고리즘 중 하나이다.