Array vs Linked List

1 분 소요

Arryay and Linked List

배열(Array)과 연결 리스트(Linked List)는 데이터를 저장하고 조작하기 위한 자료 구조라는 뜻을 가지고 있다. 하지만 각각의 구조와 특징이 다르다.

배열(Array) 특징
- 배열은 동일한 자료형의 요소들을 일렬로 저장하는 선형 자료 구조
- 메모리에서 연속적인 공간을 차지하며, 인덱스를 사용하여 요소에 접근 가능
- 요소를 삽입하거나 삭제할 경우, 해당 위치 이후의 요소들을 이동시켜야 하므로 시간이 많이 소요
연결 리스트(Linked List) 특징
- 연결 리스트는 노드(Node)들이 연결된 구조로 데이터를 저장하는 선형 자료 구조
- 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성
- 요소를 삽입하거나 삭제할 때, 해당 위치의 이전 노드와 다음 노드의 포인터만 변경하면 되므로 O(1)의 시간 복잡도를 가짐

시간 복잡도(Time complexity)는 알고리즘의 실행 시간이 입력 크기에 어덯게 의존하는지를 나타내는 개념이다.

O(n)은 상수 시간 복잡도를 나타내며, 입력의 크기와 상관없이 일정한 실행 시간을 가지는 알고리즘을 의미한다.
O(n)에서의 n은 일반적으로 입력 크기를 나타낸다.
O(n)의 시간 복잡도를 가지는 알고리즘은 입력 크기 n에 따라 실행 시간이 선형적으로 증가한다.
- 즉, 입력의 크기가 2배 증가시 알고리즘의 실행 시간도 2배로 증가한다.

삽입 및 삭제 연산:
- 배열: 요소를 삽입 또는 삭제할 때, 해당 위치 이후의 요소들을 이동시켜야 하므로 비효율적
- 연결 리스트: 요소의 삽입 또는 삭제가 상대적으로 효율적
검색 연산:
- 배열: 인덱스를 통해 요소에 직접 접근하므로 검색이 빠르며 O(1)의 시간 복잡도를 가짐
- 연결 리스트: 요소의 접근이 선형적으로 진행되므로 검색은 첫 번째 노드부터 차례로 진행되어 O(n)의 시간 복잡도를 가짐
메모리 관리:
- 배열: 메모리에서 연속적인 공간을 차지하며, 크기가 고정되어 있으며, 크기를 초과할 경우 배열을 재할당해야 함
- 연결 리스트: 메모리에서 불연속적인 공간을 차지하며, 크기가 동적으로 조정 가능하며, 필요에 따라 노드를 추가하거나 제거가 가능
저장 공간:
- 배열: 요소들이 연속적으로 저장되므로 저장 공간의 낭비가 없음
- 연결 리스트: 각 노드는 다음 노드를 가리키는 포인터를 가지고 있어 추가적인 포인터 공간이 필요
접근 속도:
- 배열: 인덱스를 통해 요소에 직접 접근하므로 접근 속도가 빠름
- 연결 리스트: 요소의 접근은 포이터를 따라가야 하므로 배열에 비해 상대적으로 접근 속도가 느림

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list