선형 자료구조 : 배열(Array), 연결리스트(linked list), 스택(Stack), 큐(Queue)

1. 자료구조(Data Structure)란?

1. 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장구조를 말한다.

2. 일반적으로 원시자료형을 기반으로 하는 배열, 연결리스트, 객체 등을 말한다.

3. 추상자료형의 실제 구현은 대부분 배열, 연결리스트를 기반으로 한다.

cf) 자료형(Data Type)이란?
: 컴파일러 또는 인터프리터에게
프로그래머가 데이터를 어떻게 사용하는지를 알려주는 일종의 데이터 속성(attribute)이다.
ex) 파이썬 언어에서 지원하는 자료형
None, 숫자[정수-불리언, 실수], 집합, 매핑(딕셔너리 복합자료형),
시퀀스[문자열, 튜플, 바이트(불변), 리스트(가변)]

원시자료형(Primitive Data Type)이란?
1. C나 JAVA 같은 성능에 대한 우선순위가 높은 언어에서 제공하는 자료형
2. 하드웨어에 좀 더 가까운 원시타입을 별도로 제공
3. 원시타입으로 구현했을 때 훨씬 더 빠른 속도로 실행할 수 있다
   (원시타입을 쓰면 메모리에서 값을 꺼내 한번 연산하면 끝)

ex) C는 동일한 정수형이라도 크기나 부호에 따라 다양한 원시타입 제공
short, long, long long, int, float, double
원시타입은 메모리에 정확히 타입 크기만큼의 공간을 할당하고 그 공간을 오로지 값으로 채워 넣는다.

4. 파이썬은 원시자료형을 지원하지 않는다. (파이썬에서 모든 것은 객체)
파이썬 같은 객체지향언어에서는 값을 꺼내기 위해
내부적으로 자료형이 뭔지 확인하는 등의 여러 단계의 부가작업이 필요하다.
(넘파이가 빠른 이유는 C로 만든 모듈이기 때문)

추상자료형(ADT : Abstract Data Type)이란?
1. 자료형에 대한 수학적 모델을 지칭한다
2. 인터페이스만 보여주는 것 = 자료형의 연산을 정의한 것 = 행동만 정의하는 것

 

 

예컨대,
스택(Stack)
LIFO (Last - In - First - Out  후입선출)

 

큐(Queue)
FIFO (First - In - First - Out 선입선출)




스택과 큐는 자료형의 연산, 그 행동만 정의돼 있고
구현 방법은 정의되어 있지 않은 추상 자료형이다.
반면,
배열은 연속적으로 저장되어 있어야 하고
연결리스트는 다음 데이터의 위치를 저장하는 방식이어야 하는 자료구조다.

3. 실제 구현 방법은 보여주지 않는다
cf) 스택은 연결리스트로도 구현할 수 있고 배열로도 구현할 수 있다.
큐도 마찬가지 ???

자료에 대한 연산의 종류
1. 자료를 변경하기 위한 연산
   ex) 스택의 경우 push, pop 

2. 자료에 대한 정보를 얻어내는 연산
   ex) 스택의 크기를 알 수 있는 size 연산 등

추상자료형이란 것을 정의하는 이유 
실제로 구현하는 방법과 그것을 사용하는 것을 구분해준다. (구현과 사용의 분리)

i.e. 파이썬에서 내장함수, 라이브러리를 가져다 쓸 때
    구체적으로 어떻게 구현되는 지에 관한 내요을 몰라도 
    그 이름만 알고 있으면 가져다 쓸 수 있는 것은
    추상자료형이 정의되어 있기 때문이다.

추상 자료형은 정해진 것이 아니다.
많이 사용되는 것들이 몇몇 정해져 있지만 자신의 구현목적에 따라 달라질 수도 있다.

cf) 추상적 자료구조란?
1 . 추상적 자료형과 비슷한 개념
2. 자료에 대한 연산을 명기하고 각 연산들의 시간복잡도까지 나타낸 것

2. 배열(Array)이란?

여러 데이터를 하나의 이름으로 그룹핑해서
그룹으로 관리하기 위한 목적으로 사용하는 자료구조

배열의 특징

1. 연속된 메모리 공간에 순차적으로 저장한다.
  연속되어 배열된 각 값(value)에는 인덱스(index)가 있고
  인덱스는 메모리의 주소를 가리킨다
  값과 인덱스를 합쳐 원소(element)라고 부른다.

2. 배열을 선언할 때 크기를 정하는데
   이렇게 정해진 배열의 크기는 변경할 수 없다.
   다시 말해, 배열의 크기는 고정돼 있다.

3. 데이터를 검색하고 확인할 때
   시간복잡도 O(1) 속도로 작업이 가능하다.
   인덱스를 가지고 있어 메모리에 저장된 데이터에
   바로 접근이 가능한 것이다.
   따라서 자료구조의 크기가 클수록 이 특징은 강력한 장점이 된다.

 

 

Random Access
임의적 접근이란 인덱스를 사용하여 바로 접근 할 수 있는 것을 뜻한다.
배열의 크기와 인덱스를 사용해서 위치를 계산하기만 하면
해당 메모리에 배치되어 있는 값을 바로 읽어올 수 있기 때문이다.
이것은 배열이 메모리에 순차적으로 저장되어 있기 때문에 가능한 것이다. 

배열의 단점

1. 메모리 상에 맨 앞 또는 중간에
  저장된 데이터를 삭제하거나, 삽입하는 경우
  작업속도가 시간복잡도 O(n)만큼 걸린다.

  메모리 공간에 연속적으로 할당했기 때문에
  해당 원소 이후의 모든 원소를 한칸씩 당기거나
  밀어야 하기 때문이다.

배열을 쓰면 좋은 경우

1. 데이터 개수가 확실하게 정해져 있을 때
2. 데이터의 삭제와 삽입이 적을 때
3. 검색을 해야할 때

파이썬에서의 배열

배열이란 고정된 크기만큼의 연속된 메모리 할당이다.
따라서
데이터의 전체 크기를 정확히 맞춰 메모리에 할당하지 못하고
너무 작은 영역을 할당하면 메모리가 모자라거나
너무 많은 영역을 할당하면 메모리가 낭비될 수 있다.

파이썬은 배열의 크기를 자동으로 맞춰주는
동적 배열 자료형(Dynamic Array)이다.

(다시 말해 위에 설명한 배열은 정적 배열이다. C언어를 기준으로 설명한 배열이다)

동적 배열 자료형을 지원하는 동적 프로그래밍 언어의 경우
데이터의 조회시 정적 배열과 같이 O(1)에 가능하면서
코딩도 매우 간편하다는 장점이 있지만
데이터가 추가되면
더 큰 크기의 배열을 할당하고 기존데이터를 복사하는 작업이 필요하므로 (이를 더블링이라하며 자동으로 이뤄진다)
O(n)의 비용이 발생한다고 한다. <<< 정확하지 않다. 분할 상환 분석 내용 추가 필요

 

3. 연결 리스트(Linked List)란?

배열(Array)처럼
데이터를 순차적으로 저장하는 선형 자료구조이지만
메모리 공간에 불연속적으로 저장된다.
다시 말해, 컴퓨터의 메모리 어딘가에 여기저기 흩뿌려져 할당된다.

연결 리스트의 특징

1. 연결리스트의 각 노드(원소)들은
   포인터를 기반으로 연결되어 리스트를 구성한다.
   첫번째 노드는 헤드(Head),
   마지막 노드를 테일(Tail).

2. 각 노드는
   데이터와
   다음 노드를 가리키는 포인터로 이루어진다.
   바꿔 말하면
   인덱스 접근이 불가능하다.
   Random Access가 불가능하다.

3. 반드시 연결된 노드를 통해서만 접근이 가능하다.
   따라서 n번째 저장된 데이터에 접근하려면
   n-1번까지 순차적으로 접근해야 한다
   (Sequential Access)

4. 따라서 리스트의 맨 앞 또는 뒤에
   데이터를 삽입, 삭제하는 경우 O(1)
   반면
   리스트의 중간에 삽입, 삭제하는 경우 O(n)

연결리스트의 장점

1. 데이터의 삽입과 삭제가 용이
   (포인터가 가리키는 노드만 변경해주면 된다)
2. 크기가 고정되어 있지 않아 크기 제한에서 자유롭다.

연결리스트의 단점

1. 검색 성능이 좋지 않다.
2. 포인터로 인하여 저장 공간의 낭비가 발생

연결리스트를 사용하는 경우

1. 크기가 정해져 있지 않을 때
2. 삽입과 삭제가 자주 일어날 때
3. 검색을 자주 하지 않을 때

 

4. 스택(Stack)이란?

다음의 2가지 주요연산을 지원하는
요소의 컬렉션으로 사용되는 추상자료형이다

push() : 요소를 컬렉션에 추가한다

pop() : 가장 최근에 삽입된 요소를 제거한다

 

요소가 없으면 pop을 해도 뺄 게 없으므로 "Stack Underflow" 에러가 발생한다
반대로 스택의 크기, 즉 배열의 크기 이상의 자료를 Push 하면 "Stack Overflow" 에러가 발생한다

스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을수 있고,
top으로 정한 곳을 통해서만 접근할 수 있다.

스택 사용 사례

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

스택은 콜 스택(Call Stack)이라 하여 컴퓨터 프로그램의 서브 루틴에 대한 정보를 저장하는 자료구조에도 널리 활용된다  ???

5. 큐(Queue)란?

시퀀스의 한쪽 끝에는 entity를 추가하고

다른 반대쪽 끝에는 제거할 수 있는

entity 컬렉션이다.


정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리
큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 이루어진다.
이때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)라 부른다.

큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue) 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부른다.

그밖에
큐를 일반화한 데크(Deque),
큐의 문제점을 해결하기 위한 원형큐,
우선순위 큐 등이 있다.

큐 사용 사례

• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

파이썬에서의 스택과 큐
파이썬은 스택, 큐 자료형을 별도로 제공하지 않는다.
리스트가 스택, 큐의 모든 연산을 지원한다.
(파이썬의 lists는  임의의 데이터 타입을 담을 수 있는 가변적 연속열(sequence)이다. 즉 동적 배열이다.)

파이썬의 list 1. 서로 다른 타입의 자료형을 원소로 가질 수 있다. 2. 자료구조상 연결 리스트의 기능을 가지고 있지만 실제로는 array로 구현돼 있다? (원소들이 연속된 메모리 공간에 배치)	파이썬의 array (넘파이도 array다) 1. array는 element들이 연속된 메모리 공간에 배치된다. 2. 모든 element들은 동일한 크기와 타입을 가져야 한다. 3. array는 처음부터 element 의 타입을 지정해서 생성한다  4. element를 추가할 때도 다른 타입은 허용되지 않는다
l = [1, 2, 3, "4", [1, 2, 3], (1,2)] l.append(0.5)    # 가능 l.insert(4, {'k':1, 'v':2})    # 가능	import array as arr ar = arr.array('i', [1,2,3])   # 가능 array( 'i', [1, 2, 3])  'i'는 자료형을 의미 int ar.insert(1,5)    # 가능 ar.append('4')    # 불가능	import numpy as np npar = np.array([0, 1, 2, 3, '4'])    # 가능 array(['0', '1', '2', '3', '4'], dtype= '<U21') 원소들을 모두 문자열로 맞춰서 배열 생성  npar2 = np.array([0, 1, [2, 3], 4])   # 가능 array([0, 1, list([2, 3]), 4], dtype = object) 원소들의 dtype을 object로 맞춰서 배열 생성

그러나 좀 더 나은 성능을 위해서는 양방향 삽입, 삭제가 모두 O(1)에 가능한
데크를 사용하는 편이 가장 좋다.
(파이썬에서 리스트는 동적 배열로 구현돼 있어 큐의 연산을 수행하기에 효율적이지 않다)




자료 출처

위키피디아

파이썬 알고리즘 인터뷰 책

blog.martinwork.co.kr/theory/2018/09/22/what-is-difference-between-list-and-array.html

devuna.tistory.com/22

winplz.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%8A%A4%ED%83%9D%EA%B3%BC-%ED%81%90-stack-and-queue