정적 배열은 크기가 고정 되어잇어 크기를 동적으로 변경하기 어려움, 동적 배열을 사용 할 수 있으나 가득 차면 배열을 2배로 늘려서 공간을 확보합니다.
시간 복잡도
접근
배열은 랜덤 접근 (Random Access)
특정 인덱스에 위치한 원소에 접근하는 경우 - O(1)
검색 (순차 접근)
선형 검색 : 특정 값이 있는 인덱스를 찾는 경우 - O(n)
이진 탐색 (Binary Search) : 정렬된 배열에서 특정 값을 찾는 경우 - O(log n)
삽입
배열의 시작에 원소를 삽입하는 경우 - O(n)
배열의 중간 위치에 원소를 삽입하는 경우 - O(n)
배열의 끝 위치에 원소를 삽입 하는 경우 - O(1)
Linked List
연결 리스트는 배열과 비교 헀을 때, 삽입 / 삭제 연산에 효율적인 자료 구조
데이터 요소들이 순서대로 연결되어 있는 선형 자료 구조이면서, 원소가 추가 될 때 마다 공간을 할당받아 비 연속적인 메모리 공간에 추가합니다.
크기가 동적으로 조정 가능해서 공간 효율적입니다.
각 요소(Node)는 데이터와 다음 요소를 가리키는 포인터(주소)로 이루어진다. data에 저장 되는 값은 정수, 실수와 같은 기초 타입이나 클래스의 객체가 될 수 있습니다.
시간 복잡도
접근
특정 인덱스에 위치한 원소에 접근하는 경우 - O(n)
검색
특정 인덱스에 위치한 원소에 접근하는 경우 - O(n)
삽입
연결 리스트 시작에 원소를 삽입하는 경우 - O(1)
연결 리스트의 중간에 원소를 삽입하는 경우 - O(n)
Linked List의 장점과 단점
장점
동적 크기 : 배열과 달리 링크드 리스트는 고정된 크기를 갖지 않음. 따라서 메모리 사용이 효율적이며 필요에 따라 리스트의 크기를 동적으로 변경 가능
삽입 및 삭제 용이 : 배열에서는 원소를 삽입하거나 삭제 할 때 해당 위치 뒤의 모든 원소를 이동 해야 합니다. 반면, 링크드 리스트에서는 특정 위치에 원소를 삽입하거나 삭제 할 때 해당 노드의 포인터만 변경하면 되므로 O(1)의 시간 복잡도로 연산을 수행 할 수 있습니다. (단 삭제나 삽입을 위해 특정 노드를 찾는 데 추가적인 시간 필요)
메모리 할당 : 링크드 리스트는 노드를 필요에 따라 동적으로 할당하므로, 초기 메모리 할당이 필요하지 않습니다.
단점
메모리 사용 : 각 노드는 데이터와 포인터를 저장해야 하므로 추가적인 메모리가 필요합니다. 이로 인해 배열에 비해 메모리 사용이 비효율적일 수 있습니다.
순차 접근 : 링크드 리스트는 인덱스 기반의 접근을 제공하지 않습니다. 따라서 특정 노드에 접근하려면 헤드부터 순차적으로 탐색해야 합니다.
복잡성 : 링크드 리스트는 포인터를 사용하여 노드들이 연결되어 있기 때문에, 연산이 배열보다 복잡해 질 수 있습니다. 이중 연결 리스트나 원형 연결 리스트에서는 더 복잡한 연산이 필요합니다.
역순 탐색의 어려움 : 단일 연결 리스트의 경우, 역순으로 리스트를 탐색하는 것이 어렵습니다. 이를 해결 하기 위해 이중 연결리스트를 사용 할 수 있짐나, 이는 추가적인 메모리를 필요로 합니다.
단일 / 이중 / 원형 연결리스트
Singly Linked List
각 요소가 다음 요소만 가리키는 단일 방향 구조
노드가 데이터와 다음 노드를 가리키는 포인터 하나로 이루어짐
단점
마지막 노드의 링크(next)가 null 값을 가지고 있는 구조에서 첫 노드와 마지막 노드에 대한 접근성이 극적으로 차이남
원소 수가 n이라면 원소를 맨 앞에 삽입/삭제 할 때는 상수 시간 O(1)이 드는 반면 맨 끝에 삽입/삭제 할 때는 O(n) 시간이 든다.
사용사례
Stack & Queue : 단일 연결 리스트는 스택 및 큐의 구현에 주로 사용됩니다. 이는 삽입 삭제 연산이 O(1)의 시간 복잡도를 가지기 때문입니다.
재귀 알고리즘 : 단일 연결리스트는 재귀 알고리즘이나 함수 호출을 구현하는데 유용합니다. 이는 노드를 쉽게 추가하거나 제거 할 수 있기 때문입니다.
Memory Management : 연속적인 메모리 할당이 필요 하지 않은 경우에 단일 연결리스트를 사용하여 메모리를 효율적으로 관리 할 수 있습니다.
Doubly Linked List
단일 연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성 되어 있다. 반면, 이중 연결 리스트는 각 노드가 데이터와 이전 노드, 다음 노드를 가리키는 두 개의 포인터로 구성 되어잇다.
각 요소가 이전 요소와 다음 요소를 모두 가리키는 이중 방향 구조
노드가 데이터와 이전 노드, 다음 노드를 가리키는 포인터로 이루어짐
사용 사례
양방향 탐색이 필요한 경우
텍스트 에디터 구현
페이징 처리
시각화 도구의 표현
데이터 삽입/삭제 가 빈번한 경우
자료의 정렬 및 재정렬이 필요한 어플리케이션
캐시 구현 (LRU Cache등)
작업 큐 관리
Real-Time Collaboration Tools
Circular Linked List
마지막 요소의 포인터가 첫 요소를 가리키는 형태로 구성된 연결 리스트
원형 구조로 인해 순환적인 작업이 필요한 상황에서 사용됨 (예: 순환 알고리즘, 반복적인 작업)
사용 사례
순환 버퍼 (Circular Buffer)의 구현 (ex 실시간 스트리밍, 일정 시간 동안만 최신 데이터를 유지하고 싶을때)