배열, 스택, 큐, 연결리스트

배열의 선언 방법

정적 VS 동적

정적 배열은 프로그래밍 시에 배열의 길이가 정해지도록 선언하는 방법을 말한다. 하지만고정으로 배열을 선언했을 때 배열의 길이를 바꿀 수 없다. 예를 들어 IF A[100]을 선언했다면 1000개의 데이터를 저장할 수 없다. 하지만 동적 배열 선언시엔 배열의 길이를 가변적으로 조절 할 수 있다. 예를들어 처음에 10개의 배열을 선언했다가 추가로 100개를 저장해야할때는 A라는 배열을 동적할당을 통해 10개로 선언했다면 새로이 B라는 배열을 동적할당을 통해 선언하고 A에 저장된 요소를 B에 복사한다. 그 후에 A를 할당해제하고 A를 B에 pointing한다. 그러면 A는 100개의 요소를 가진 배열이 된다.

배열의 특징:

1. 숫자인덱스를 기반으로 랜덤접근이 가능하고 중복을 허용한다. (이는 연결리스트는 안되는 특징임)

2. 컴파일 시점에 사용해야 할 요소들의 개수를 모른다면 vector를 사용하기(동적으로 요소를 할당할 수 있는 동적 배열)

3. 시간복잡도는
   참조: O(1) ->랜덤접근이 가능함
   탐색: O(n) -> 쭉 돌아서 다 찾아야함
   맨 끝에 삽입/삭제: O(1) -> 바로 삽입/삭제하기
   맨 끝 제외 삽입/삭제: O(n) ->최악의 경우 O(n)

array와 vector와 같은 배열은 같은타입의 변수로만 이루어져있고 크기가 저정해져있으며, 인접한 메모리위치에 있는 데이터들을 모아놓은 집합이다.

스택

한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out: LIFO) 형태의 선형 자료구조이다.즉, 가장 최근에 들어온 데이터가 가장 먼저 나가는 구조!
재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다.

스택의 구조를 보면 이와 같다.

스택의 주요 연산으로는

1.데이터(element)를 스택에 추가/삽입 (push)
2.데이터(element)를 스택에서 제거 (pop)
3.스택이 가득 차 있는지 확인 (full)
4.스택이 비어있는지 확인 (empty)
맨 위의 element를 꺼내지 않고 무엇인지 확인 (peek)
5.element 개수 확인 (size)
대표적으로 5가지가 존재한다.

스택 분석

시간복잡도:

1. n번쨰 참조: O(n) -> 최악의 경우
2. 가장 앞부분 참조: O(1)
3. 탐색: O(n)
4. 삽입/삭제(n번째 제외): O(1) -> n개의 데이터를 push하는데 요구되는 시간복잡도는 o(n)이다.

메서드:
1. push(value)-> 해당 value를 스택에 추가
2. pop() -> 가장 마지막에 추가한 요소를 지움
3. top() -> 가장 마지막에 있는 요소를 참조
4. size() -> 스택의 크기.

큐

큐는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO:First-InFirst-Out)을 지닌 자료구조이다. CPU작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비우선 탐색, 캐시 등에 사용된다. 쉬운 예로는 매표소의 대기열이 있다.

큐의 동작원리

큐의 시간복잡도

1. n번째 참조: O(n)
2. 가장 앞부분 참조: O(1)
3. 탐색: O(n)
4. 삽입/삭제(n번째 제외): O(1) -> n번째 삽입, 삭제는 O(n)이다.

메서드:
push(value): value를 큐에 추가
pop(): 가장 앞에 있는 요소 제거
size(): 큐의 크기
front(): 가장 앞에 있는 요소 참조

연결리스트

기존 자료구조인 스택과 큐는 삽입/제거의 형식만 다를 뿐 기본적으로 배열로 구현되어있는 성질을 가지고 있다.
배열의 경우 요소 접근 및 탐색이 용이하지만 요소의추가 삭제가 어렵다는 단점을 가지고있다. 예를 들어 배열은 특정 길이를 먼저 선언한 후에 요소를 저장할수 있기 때문이다. 그래서 배열과 같은 형식이지만 요소의 추가/삭제가 용이한 자료구조가 필요한데 그래서 LIST가 등장하였다.
연결리스트는 요소를 저장하는 길이에 제한이 없는 자료구조이고 삽입/제거가 용이한 자료구조이다. 요소들을 노드라고 하는 곳에 분산하여 저장한다. 이때 노드는 데이터필드와 링크필드로 구성되는데 데이터필드는 값을 저장하는 곳이고, 링크 필드는 다른 노드의 주소값을 저장하는 장소(포인터)를 의미한다.
요약하자면 연결리스트는 노드로 감싸진 요소를 인접한 메모리 위치가 아닌 독립적으로 저장하며 각 노드는 next 또는 next, prev 라는 포인터로 서로 연결된 선형적인 자료구조이다.

연결리스트 장단점

장점: 1. 삽입, 삭제가 용이하다.
2. 연속된 메모리 공간이 필요없다.
3. 크기 제한이 없다.

단점: 1. 구현이 어렵다.
2. 오류가 발생하기 쉽다.
3. 많이 연습해야한다.

연결리스트에서의 삽입(add/push)

Idea:Node를 추가하고,연결!

void add(List* list, int value):
새로운 Node를 만든다.
새로운 Node의 value를 value로 설정한다.
List에 저장된 마지막 Node의 next를 Node의 주소로 설정한다.

연결리스트에서의 제거(remove/ pop)

Node를 하나씩 제거!

연결리스트에서의 탐색 (search/contains)

Node를 하나씩 순회!
순회를 하면서, 찾는 값이 있는 지 확인!

연결리스트의 시간복잡도

참조: O(n) -> 노드를 하나하나 다 봐야 알수있기 때문
탐색: O(n) -> 마찬가지로 노드를 하나하나 다 봐야함
삽입/삭제: O(1)-> 그냥 그 자리에서 바로 삽입하고 삭제할 수 있음

연결리스트의 종류

싱글 연결리스트(Singly Linked List): next포인터밖에 존재하지 않으며 한 방향으로만 데이터가 연결된다.

이중연결리스트(Doubly Linked List)는 prev, next 두개의 포인터로 양방향으로 데이터가 연결된다.

원형연결리스트(Circular Linked List)는 마지막 노드와 첫번째 노드가 연결되어 원을 형성한다.