연결 리스트는 동적배열과 마찬가지로 배열의 단점을 보완하기 위해 만들어진 자료구조이다.

그렇다고해서 연결 리스트나 동적배열이 항상 배열 보다 좋다는 의미는 아니다. 

상황마다 장단점이 있기 때문에 자신의 필요에 따라 사용하면 된다.

C++에서는 STL 의 list , 자바에서는 LinkedList 로 표준 라이브러리에 구현되어 있다.

연결 리스트(Linked list) 란?

 연결 리스트란 자료구조의 각 부분부분인 노드들이 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 노드는 데이터를 담는 박스 같은 개념으로 생각하면 된다.

연결리스트는 택배박스를 생각하면 쉽다. 

물건(데이터)이 담긴 택배 박스(노드)를 보면 보낸 곳(이전 노드 포인터)과 보낼 곳(다음노드 포인터)이 쓰여 있다. 여기서 포인터는 현실에서 처럼 주소값을 의미한다.

연결 리스트는 각 노드에 이전과 다음 노드에 대한 포인터를 가지고 있어 배열과 다르게 메모리 여기저기에 노드들이 흩어져 있다.

연결 리스트가 필요한 이유

 연결 리스트는 노드들 사이에 데이터를 삽입하거나 삭제하는 작업이 많을 때 필요하다.

노드에 이전 데이터와 다음 데이터의 포인터를 가지고 있어서 삽입과 삭제 작업을 O(1)에 처리 할 수 있기 때문이다. ( 포인터만 바꿔주면 된다! )

만약 배열로 이러한 작업들을 하게 되면 평균적으로 데이터 개수에 선형 비례하는 시간이 소요되어 비효율 적이다. 배열에서는 중간에 데이터를 삽입하거나 삭제할 때 데이터들을 한칸 씩 옮겨야 해서 

시간복잡도가 O(n) 이다.

하지만 특정 위치의 데이터를 찾는 작업에서는 시간복잡도가 O(n) 이기 때문에 오히려 배열 보다 비효율 적이다. (배열은 데이터 검색 시 시간복잡도가 O(1) 이다. )

연결 리스트에서 데이터가 추가되는 경우

연결 리스트에서 데이터가 삭제되는 경우

연결 리스트의 종류

연결 리스트에는 대표적으로 3가지 종류가 있다.

1. 단일 연결 리스트

단일 연결 리스트는 각 노드에 데이터와 다음 노드를 가리키는 포인터가 담겨있다.

가장 단순한 형태의 연결 리스트다.

2. 이중 연결 리스트

이중 연결 리스트는 각 노드에 데이터와 이전 노드와 다음 노드의 포인터가 담겨있다.

단일 연결 리스트에서는 각 노드가 다음 노드는 알고 있으나 이전 노드를 알지 못해 이전 노드로 접근할 수가 없다. 이러한 단점을 보완하기 위해 이중 연결 리스트가 생겨났다.

3. 원형 연결 리스트

원형 연결 리스트는 단일 연결 리스트에서 마지막 노드와 처음의 노드를 연결시켜 원형 구조로 만든 것이다. 단인 연결 리스트는 임의의 노드 위치에서부터 이전에 위치한 노드에 접근할 수 없기 때문에 원형 구조를 만들어 순환해서 접근할 수 있도록 만든 것이다. 

 배열이란 같은 종류의 데이터들 일렬로 저장하는 자료구조이다. 

배열에 저장된 각 데이터들은 번호(index)를 가지고 있다.

하지만 이러한 배열만으로는 비효율적이거나 한계가 있는 작업이 있기 때문에 동적배열이나 연결 리스트 등과 같은

자료 구조를 만들어 사용한다. 

(동적배열이든 연결 리스트든 모두 기본적으로 배열을 이용하여 만들어낸 자료구조이다.)

동적배열(Dynamic Array) 이란?

 동적 배열이란 크기가 고정되지 않은 배열을 의미한다. (이름 그대로 단순하다!)

보통 우리가 흔히 말하는 배열은 동적(Dynamic)의 반대인 정적(Static) 즉, 정적배열을 의미한다. 정적배열은 크기가 고정되어 있어 데이터를 크기 만큼만 저장할 수 있다.

대표적으로 C++ 의 vector 나 자바의의 ArrayList 등이 있다.

동적배열이 필요한 이유

 동적배열은 이름에서 나타나듯이 배열의 크기를 동적으로 늘려서 사용하고 싶을 때 필요하다. (이유도 단순하다!)

배열은 크기가 고정해야 되기 때문에 이를 해결하기 위해 동적배열이 고안된 것이다.

처음부터 자신이 사용할 배열의 크기를 알면 좋겠지만 크기를 너무 크게 잡으면 메모리가 낭비되고, 그렇다고 크기를 작게 잡으면 매번 배열을 새로 만들어서 기존의 배열을 옮겨 담아야 해서 번거롭다.

동적배열의 시간복잡도

1. 특정 위치의 데이터를 반환하거나 변경하는 작업을 시간복잡도 O(1) 에 처리할 수 있다. 

(배열과 공통)

동적배열은 배열을 이용하여 구현되어 있기 때문에 데이터들이 메모리의 연속된 위치에 저장되어 있고, 각 데이터들은 번호(Index)를 가지고 있다. 그래서 특정 위치의 데이터를 호출하거나 변경하는 O(1)에 처리할 수 있다.

 자료구조는 자료(데이터)를 효율적으로 접근하고 수정하기 위해 자료를 조직,관리,저장하는 방법을 의미한다.

자료구조가 필요한 이유는 상황에 따라 데이터를 다루는데 시간과 메모리를 효율적으로 사용해야 때문이다.

자료구조는 형태에 따라 크게 선형 자료구조와 비선형 자료구조로 나뉘어 진다. 

선형 자료구조란 자료를 구성하는 데이터들이 직선 형태로 순차적으로 나열되어 있는 구조로 전후 데이터들 간에 일대일( 1:1 ) 관계이다.

비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 구조로 전후 데이터들 간에 1:N 의 관계를 가진다.

자료구조에서 선형구조에는 대표적으로 스택(stack), 큐(queue), 덱(deque), 리스트(list) 등이 있고,

비선형구조에는 트리(tree), 그래프(graph) 등이 이다. (실제로는 더 다양하다.)

스택(stack) 이란?

  스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 후입 선출 (Last In First Out , LIFO)의 자료구조이다.

쉽게 생각하면 stack 의 뜻처럼 쌓는걸 의미한다 생각하고, 하노이의 탑과 같다고 생각하면 되겠다.

큐(queue) 란?

 큐는 한 쪽 끝에서 데이터가 삽입되고, 다른 한 쪽 끝으로 삭제 되는 선입 선출(First In First Out, FIFO)의 자료구조이다.

마치 차들이 1차선 터널을 통과하는 것과 같다. queue 의 뜻이 줄을 서서 기다리는걸 의미하니 음식점 앞에 줄서 있는 구조라 생각해도 되겠다.

덱(deque) 이란?

 덱은 스택과 큐가 결합한 자료구조로 양쪽 끝에서 데이터들을 넣고 뺄 수 있다.

자료구조에서는 데이터를 넣는 작업을 push , 자료를 꺼내는 작업을 pop 이라고 한다.

대부분의 프로그래밍 언어에서 표준라이브러리로 스택, 큐, 덱의 구현체를 제공하고 있다.

 컴퓨터 과학(Computer Science) 에서 알고리즘은 어떠한 문제를 해결하기 위한 방법이고,

어떠한 문제를 해결 하기 위한 방법은 다양하기 때문에 방법(알고리즘) 간에 효율성을 비교하기 위해

빅오(big-O) 표기법을 보통 가장 많이 사용한다.

(결국은 알고리즘 공부를 하려면 배워야한다는..)

빅오 표기법 (big-O notation) 이란?

 빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다. 

쉽게 생각하면 알고리즘 스카우터라 생각하면 된다 :)

알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.

빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.

(시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)

그런데 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 

빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.

그렇다면 세 가지 중 왜 빅오 표기법을 사용할까?

 결론부터 말하자면 빅오 표기법은 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다. (알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.)

빅오메가는 하한선을 기준으로하고, 빅세타는 상한선과 하한선의 사이를 기준으로 표기한다.

일상의 대화에서 비유하자면 법정 최고이자율이 24% 인데 친구가 사채대출의 이자율을 물어본다.
(이자율이 높을수록 최악의 경우이다.)

하지만 정확한 법정 최고이자율이 생각나지 않는다.

이때 친구에게 빅오 표기법으로 말하자면 사채대출을 받으면 이자율이 30% 안에서 책정 될거야 라고 말하는 것과 같다.

(실제로 정확하진 않지만 대략 30%를 넘지 않을 것을 알고 모든 경우의 수를 포함하도록 말하는 것이다.)

빅오메가 표기법으로 말하자면 이자율이 0% 이상 일거야 라고 말하는 것과 같다. (사실상 의미가 없다.)

빅세타 표기법으로 말하자면 이자율이 0%(하한) 와 30%(상한) 의 사이쯤 이라고 말하는 것과 같다.

(빅세타는 하한과 상한 사이 평균정도의 의미로 쓰인다.)

 여기서 주의할 점은 빅오 표기법이 상한선만 지정했을 뿐 상한선이 꼭 알고리즘 효율성의 최악의 경우는 아니라는 것이다.

예를들어 법정 최고이자율이 24% 라서 사채의 이자율은 24%를 넘을 수 없다. 내가 30% 안이라고 해서 친구가 사채의 이자가 최대 30%까지 될 수도 있겠다고 생각할 필요는 없는 것이다. 이자율이 최악으로 가장 높은 경우인 24% 가 이자율 30% 안에 포함된다는 말일 뿐이다.

빅오 표기법의 수학적 정의

 빅오 표기법이 나타내는 의미는 수학적 정의를 통해 알 수 있다. 점근 표기법 중 빅오 표기법을 보통 가장 많이 사용하기 때문에 빅오 표기법의 수학적 정의 정도만 보고 넘어가자.

빅오 표기법의 수학적 정의는

간단하게 예를들자면

은 내가 만든 알고리즘의 시간 효율성(running time) 을 의미하고 충분히 큰 값인 n과 상수 k에 대해

이라고 가정하면

   (  ) 가 성립하는 k 값이 존재하기 때문에 내가 만든 알고리즘  은 빅오 표기법을 사용하여 로 나타낼 수 있다.

추가적인 이해를 돕기 위해 아래 그래프를 보자.

내가만든 알고리즘의 시간 효율성(running time)을 보여주는 그래프가 이다.

이때  보다 충분히 큰 입력값 n 을 넣었을 때 내가만든 알고리즘 의 running time이 최악인 경우에도 점근 상한선인  을 넘을수가 없다.

이때를 빅오 표기법을 사용하여  이라고 나타내는 것이다.

(위의 예시에서는  )

빅오 표기법의 특징

1. 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.

예를들어

 와 같이 상수항은 무시하고 표기한다.

2. 영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

예를들어

와 같이 영향력이 지배적인  이외에 영향력이 없는 항들은 무시한다.

빅오 표기법 성능비교

 빅오 표기법에서 주로 사용되는 표기법은 아래 그래프와 같다.

그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같다.

(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

faster    slower

( 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수 )

빅오 표기법 예제

 빅오 표기법의 예제는 어떤 것들이 있는지 정도만 외워두고 알고리즘 공부를 해보면서 이해해 나가면 될 것 같다.

1. O(1) : 스택에서 Push, Pop

2. O(log n) : 이진트리

3. O(n) : for 문

4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

5. O(): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

6. O() : 피보나치 수열