[STUDY] 자료구조(Data Structure) - 선형 자료구조(Linear Data Structure)

1. 자료구조 

 

1) 자료구조란 ?

· 데이터(data)에 접근하고 제어하기 위해 데이터를 구성 및 저장하는 방법

· 데이터와 데이터 간의 관계

 

2) 구성

선형 자료구조 (Linear Data Structure)	비선형 자료구조(Non-Linear Data Structure)
· 데이터들이 순차적으로 나열되는 자료구조 · 데이터와 데이터 간의 관계가 1:1인 구조	· 데이터와 데이터 간의 관계가 1:n 인 자료구조
· 리스트 (List), 스택(Stack), 큐(Queue), 데크(Deque)	· 트리(Tree), 그래프 (Graph)

 

2. 선형 자료구조 (Linear Data Structure)

 

1) 리스트 (List) 

· 가장 기초적이고 단순한 형태의 자료구조 ( Python - list, Javascript - array )

· 선형 리스트(Linear list) 

  ① 데이터를 순차적으로 저장하는 연속된 메모리 형식 

  ② 데이터 삽입(push), 삭제(pop) 시 순서에 변함 없음 

 

  장점 : 데이터가 연속된 메모리에 저장되기 때문에 순차탐색 및 접근이 빠름

  단점 : 중간의 데이터에 삽입 또는 삭제를 위해 앞/뒤 데이터를 옮겨야하는 과정이 추가됨 

 

· 연결형 리스트(Linked list) 

  ① 데이터 단위는 노드(node)이며, 노드는 데이터와 이전 또는 다음 노드의 메모리 주소 값으로 구성(포인터)

  ② 논리적으로 데이터를 순차적으로 저장, 물지적으로 데이터는 순차적으로 저장되지 않음 
  ③ 연결형 리스트에는, 단순 원형 연결리스트(Single Circular Linked List), 이중 연결 리스트 (Doubly Linked List), 이중 원형 리스트(Doubly Circular Linked List) 가 있다.

  ※ 일반 노드는 다음 노드의 주소 값만을 포함하지만, 이중(doubly) 리스트는, 이전 / 다음 노드의 주소 값을 모두 포함 

 

  장점 : 리스트 보다 데이터 삽입, 삭제가 빠르고, 포인터 기반으로 전체 데이터 크기가 가변적이기 때문에 메모리 관리가 용이
  단점 : 데이터와 노드 주소 값이 저장되기 때문에 리스트 보다 많은 메모리를 사용하고 탐색이 늦음 

 

2) 스택 (Stack) 

· "쌓아 올린다." == Last In, First Out (LIFO)
· 한 방향으로 데이터 삽입(pop,  from Front or Top), 삭제(push, from Front or Top)가 발생 
· 빈 메모리 공간(스택)에서 데이터를 삭제 할 경우 스택 언더 플로우(stack under flow) 또는 꽉 찬 메모리 공간(스택)에서 데이터를 삽입할 경우 스택 오버 플로우(stack over flow)가 발생할 수 있음
※ 브라우저의 이전 페이지, 실행 취소(undo) 등

 

장점 : 데이터 삽입, 삭제 속도가 빠름 
단점 : 탐색(search) 느림 (탐색 위해서 데이터의 위치 변경이 필요)

 

3) 큐 (Queue)  

· "줄을 서다." == First In, First Out (FIFO)
· 한 방향에서는 데이터의 삽입(enqueue, from Rear), 다른 방향에서는 삭제(dequeue, from Front)가 발생
· 데이터의 삽입, 삭제가 빈번하게 발생할 경우, 삽입이 이루어진 입구(rear)와 삭제가 이루어지는 출구(front)의 경계가 일시적으로 닿아 데이터가 빈 상태이지만 오버 플로우(over flow)를 발생시키기도 함 
※ 줄을 서고 대기하여 순차적으로 처리하는 방식

 

장점 : 데이터 삽입, 삭제 속도가 빠름 
단점 : 스택(Stack)과 마찬가지로 탐색(search) 느림 

 

4) 데크 (Deque) 

· 스택(stack)과 큐(queue) 각각의 장점을 모두 수용 

장점 : 데이터 삽입, 삭제가 빈번한 경우 속도가 리스트(List) 보다 월등히 빠름 
단점 : 구현 난이도가 어려움