선형 구조(Linear Structure)
순차 리스트(Sequential List)
순차 리스트란 데이터를 순차적(연속적)으로 메모리에 저장한 자료 구조를 의미한다.
일반적으로 ArrayList가 여기에 속하며, 크기가 정적인 Array와 달리 크기가 가변적이어서
필요에 따라서 요소를 추가하거나 제거할 수 있다.
외의 특징으로는 아래와 같이 나타낼 수 있다.
- 탐색속도가 빠르다
- 중간에 데이터 추가/삭제 시 속도가 느리다.
인덱스를 통해 조회를 할 수 있어 탐색 속도는 빠르다는 장점이 있지만,
중간에 데이터를 추가/삭제하려고 한다면 순차적인 구조를 위해 데이터를 모두
밀거나 당겨오는 작업이 선행되어야 하기에 속도가 느리다는 단점이 있다.
연결 리스트(Linked List)
연결 리스트에서는 노드라는 개념이 등장한다.
이 노드는 데이터와 포인터를 가지고 있으며 한 줄로 연결되어 선형 구조를 이룬다.
포인터는 다음 혹은 이전의 데이터에 연결을 담당하여 어디로 연결되는지를 나타내고
이 구조에 따라서 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트로 나뉘게 된다.
따라서 데이터를 유동적으로 저장할 수 있다는 장점이 있지만, 접근 속도가 느리다는 단점이 있다.
아래와 같이 노드의 형태를 나타낼 수 있는데 이 노드가 연결된 집합을 연결 리스트라고 지칭하며,
연결 리스트의 맨 첫 노드를 head, 마지막 노드를 tail이라고 부른다.
또, 현재 노드 이전의 노드를 prev, 다음 노드를 next라고 부르기도 한다.
단일 연결 리스트(Singly Linked List)
단일 연결 리스트는 아래의 그림과 같이 노드의 포인터가 단일 방향으로만 연결 되었다고 보면 된다.
하나의 노드에는 데이터와 포인터가 존재하기에 탐색을 위해서는 데이터를 조회하고 포인터를 따라
다음 노드의 위치를 찾아가 데이터를 조회하는 방식의 과정을 거치게 된다.
또, 추가/삭제는 들어가려는 노드의 위치에 따라서 앞, 뒤의 포인터를 교체하는 과정을 거쳐야한다.
이중 연결 리스트(Doubly Linked List)
이중 연결 리스트는 단일 연결 리스트와 다르게 노드와 노드가 서로 연결되었다.
따라서 단방향 연결로 인해서 내 이전의 노드가 무엇인지를 모르던 단일 연결 리스트와 다르게,
양방향 연결이 되어있고 내 이전 노드와 이후 노드를 알고 있기에 탐색이 양방향으로 가능하다.
추가/삭제의 경우는 단일 연결 리스트와 매우 흡사하나 양방향으로 연결해야 한다는 점만 차이가 있다.
장점은 앞서 말한대로 양방향 탐색이 가능하다는 점이고,
단점은 구현이 조금 더 복잡하고 이전 노드를 지정하기 위해 메모리를 더 사용한다는 점이 있다.
그러나, 단점에 비해 장점이 더 유용해서 대부분 연결 리스트를 사용할 땐 이중 연결 리스트를 사용한다.
원형 연결 리스트(Circular Linked List)
원형 연결 리스트는 마지막 노드가 첫 노드를 가리키면서 구조가 원형으로 이어지는 것처럼 구성된 형태의 연결 리스트를 의미한다.
때문에 사실상 head와 tail의 구분이 모호해지며, tail의 next 노드는 head라는 특징을 갖는다.
따라서 반복적인 순회와 같은 기능에 있어서 보다 강점을 가지게 된다.
스택(Stack)
스택은 후입선출(LIFO - Last In First Out)의 구조를 갖는 자료구조이다.
데이터를 추가하는 것을 push라고 하고, 빼내는 것을 pop이라고 부르는데,
스택은 push와 pop이 모두 한 쪽의 끝에서만 가능하기에 후입선출의 구조를 가지게 된다.
아래와 같이 시각화 할 수 있다.
큐(Queue)
큐는 스택과 반대되는 개념으로 선입선출(FIFO - First In First Out)의 구조를 갖는 자료구조다.
데이터를 추가하고 빼내는 함수의 이름도 스택과 다르게 put과 get이라는 이름으로 사용하며,
put은 head에서만 진행되고 get은 tail에서만 진행될 수 있는 구조이다.
큐의 사이즈에 비해 많은 데이터가 들어와 더 이상 데이터를 저장하지 못하는 상태를 오버플로우(Overflow)라고 부르며, 큐에 데이터가 존재하지 않아 데이터를 꺼내지 못하는 경우를 언더플로우(Underflow)라고 부른다.
아래와 같이 시각화 할 수 있다.!
덱(Deque)
덱은 큐와 스택을 합친 형태로 양쪽 끝에서 추가, 삭제가 가능한 자료구조이다.
보통 양방향 큐라고 말하는데 속도, 성능의 장점으로 유용하게 사용된다.
