배열(array)와 연결리스트(linked list)에 대해서 알아보자
배열과 연결리스트는 둘 다 선형 자료 구조이다.
그렇다면 선형자료 구조는 무엇일까?
선형자료구조란?
선형자료구조는 요소가 일렬로 나열되어 있는 자료구조는 뜻한다.
선형자료구조의 종류로는 배열, 연결리스트, 백터, 큐, 스택이 있다.
이번 포스팅에서는 배열과 연결리스트에 대해서 알아보자.
배열(Array)이란?
배열은 동일한 데이터 유형의 요소가 인덱스로 구성된 선형 자료구조이다.
기본적인 특징으로 배열은 같은 타입의 변들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다. 또한 중복을 허용하고, 순서가 인덱스로 정해져 있다. 각 요소는 고유한 인덱스를 가지며, 해당 인덱스를 사용하요 요소에 접근할 수 있다.
위와 같은 특징 때문에 배열은 데이터를 검색하고 정렬하는 데 뛰어난 성능을 발휘한다. 따라서 배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을때 보통 사용한다.
하지만 배열의 크기는 고정되어 있으며, 크기를 종적으로 조정할 수 없기 때문에 배열에 추가 또는 삭제를 하려면 새로운 배열을 만들어야하는 단점이 있다.
배열의 시간복잡도
-
탐색
접근하고자 하는 인덱스를 알고 있다는 경우에 O(1)이며 순차적으로 탐색시에는 O(n)의 시간복잡도를 가진다. -
삽입 / 삭제 :
배열의 처음 또는 중간에 삽입 및 삭제 : O(n)
(삽입 지점 이후의 데이터를 옮겨야 하기 때문.)배열의 끝에 삽입 및 삭제 : O(1)
연결리스트(linked list)란?
연결리스트는 데이터 요소를 감싼 노드를 포인터(pointer)로 연결(link)하여 구성된 선형 자료구조이다.
각 요소는 데이터와 다음 요소를 가리키는 포인터로 구성된다. 이러한 특징 때문에 링크드리스트는 동적으로 크기를 조정할 수 있으며, 추가 및 삭제 작업에 효과적이다.
하지만 링크드리스트는 요소 하나하나를 직접확인하고 다음 노드를 확인하는 순차적인 방식이기 때문에 특정 위치의 데이터를 검색하거나 정렬하는 데는 부접합하다.
연결리스트의 시간복잡도
-
탐색 : O(n)
-
삽입 / 삭제: 삽입과 삭제 자체는 O(1)이다.
연결 리스트의 처음에 삽입/삭제 : O(1)
연결 리스트의 중간에 삽입/삭제 : O(n) (탐색시간 소요)연결 리스트의 끝에 삽입/삭제
끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) (탐색시간 소요)
배열 vs 연결리스트
😀한 눈에 알아볼 수 있게 두 가지 자료구조의 비교를 표로 정리해 보자
(시간복잡도는 일반적인 경우를 기준을 한다.)
| 구분 | 배열 | 연결 리스트 |
|---|---|---|
| 데이터의 접근 방법 | 인덱스를 사용해서 빠르게 접근 가능 | 처음부터 순차적으로 탐색해야 함 |
| 데이터의 추가/삭제 | 다른 데이터를 이동시켜야 함 | 노드의 연결만 변경하면 됨 |
| 메모리 사용량 | 고정된 크기로 미리 할당해야 함 | 필요한 만큼 동적으로 할당 가능 |
| 속도 | 데이터 접근에 빠름 | 데이터 추가/삭제에 빠름 |
| 구현 난이도 | 구현이 상대적으로 쉬움 | 구현이 복잡함 |
| 데이터의 탐색 | O(1) | O(n) |
| 데이터의 추가 | O(n) | O(1) |
| 데이터의 삭제 | O(n) | O(1) |
참고자료(출처)
데이터 드리븐 마케팅 Blog
면접을 위한 CS 전공지식 노트 (도서)
Velog Haileypark.log 포스팅 [자료 구조] 배열 & 연결 리스트 (Array & LinkedList)
