📚 자료구조
효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 뜻한다.
그렇다면 우리는 왜 자료구조를 알아야 할까.
우리는 메모리를 효율적으로 사용하고 데이터를 빠르고 안정적으로 처리해야 한다.
하지만 A 상황에서는 유용하게 사용될 수 있는 자료구조가 B 상황에서 느리고 비효율적일 수 있다. 그렇기 때문에 우리는 상황에 맞는 자료구조를 고를 수 있는 능력이 필요하고, 그렇기 때문에 자료구조를 잘 알아야 한다.
💻 복잡도
복잡도는 알고리즘이 수행되는 데 걸리는 시간이나 필요한 공간을 평가하는 기준을 제시한다. 복잡도를 잘 이해함으로써 자료구조의 장단점을 파악할 수 있고, 적절한 자료구조를 선택할 수 있다.
시간 복잡도 & 공간 복잡도
1. 시간 복잡도
시간 복잡도는 알고리즘이 수행되는 데 걸리는 시간을 입력 크기와 관련지어 표현하는 것이다. 시간 복잡도를 통해 입력 크기가 커질수록 알고리즘이 얼마나 느려질 수 있는지 예측할 수 있다. 이는 알고리즘의 효율성을 평가하는 주요 척도 중 하나다.
빅오 표기법
시간 복잡도를 표현할 때는 일반적으로 빅오(Big-O) 표기법을 사용한다. 빅오 표기법은 입력 크기 𝑛에 따른 최악의 경우 알고리즘 수행 시간을 표현한다.
2. 공간 복잡도
공간 복잡도는 알고리즘이 수행될 때 필요한 메모리의 양을 입력 크기에 따라 표현하는 것이다. 시간 복잡도처럼 빅오 표기법을 사용하여 알고리즘이 메모리를 얼마나 효율적으로 사용하는지 나타낸다.
선형 자료 구조
선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다.
선형 자료 구조에는 연결 리스트, 배열, 스택, 큐가 등이 있다.
하나씩 알아보자
1. 연결 리스트
연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조다.
연결 리스트의 종류
- 단일 연결 리스트
- 단일 연결 리스트에서 각 노드는 데이터와 포인터를 가진다. 데이터에는 실제 정보를 저장하고 포인터에는 다음 노드의 주소를 저장한다.
- 이중 연결 리스트
- 이중 연결 리스트는 각 노드에 이전 노드에 대한 포인터와 다음 노드에 대한 포인터를 갖고 있기 때문에 양방향으로 순회할 수 있다. 이를 통해 리스트에서 노드를 빠르고 쉽게 삽입하고 삭제할 수 있다.
- 원형 단일 연결 리스트
- 원형 단일 연결 리스트 노드에는 다음 포인터만 있다. 하지만 마지막 노드의 다음 포인터는 첫 번째 노드를 가리키기 때문에 원을 형성한다.
2. 배열
배열은 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다.
배열의 특징을 연결리스트와 비교하며 알아보자
- 배열은 데이터를 순서대로 나열하기 때문에 인덱스 값만 알면 해당 인덱스에 있는 값을 참조할 수 있다. 연결리스트는 매번 노드와 포인터를 통해 접근하기 때문에 O(n)의 시간 복잡도를 갖지만, 배열은 인덱스 값으로 접근하기 때문에 O(1)의 시간 복잡도를 갖는다.
- 데이터를 추가하고 삭제하는 경우에는 연결리스트가 더 빠르다. 연결리스트에서는 선을 바꿔서 연결하기만 하면 되지만, 배열에서는 데이터를 삭제하거나 추가하게 되는 경우 나머지 모든 데이터들을 한 칸씩 이동 시켜야하기 때문에 더 오래 걸린다.
3. 스택
스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질 LIFO(Last In Fisrt Out)을 가진 자료 구조다.
4. 큐
큐는 스택과 반대로 먼저 집어 넣은 데이터가 먼저 나오는 성질 FIFO(Fisrt In First Out)을 지닌 자료구조다.
