[자료구조] 배열과 리스트(Array & List)

<배열과 리스트의 차이>

 

배열

배열이란

연관된 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 선형 자료구조로

배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있으며,

반복문과 결합하여 효율적으로 데이터를 처리할 수 있다.

주로 데이터의 개수가 정해져 있는 경우나 데이터의 수정이 적은 경우,

혹은 데이터의 검색이 빈번한 경우에 사용하는 선형 자료구조형이다.

배열의 특징으로는 배열안의 데이터들은 같은 자료형으로 나열되있다는 것,

그리고 데이터가 연속된 메모리 공간에 순차적으로 저장 된다는 것,

그래서 배열의 논리적 순서(인덱스)와 원소값의 물리적인 순서(메모리 주소)

두가지가 동일하다는 것 등을 꼽을 수 있다.

 

배열에서의 시간 복잡도

삽입/삭제

-배열의 맨 앞에 삽입/삭제: O(n)

-배열의 맨 뒤에 삽입/삭제: O(1)

-배열의 중간에 삽입/삭제: O(n)

탐색: O(1)

※위와 같이 시간 복잡도가 되는 이유는 배열의 원소가

키(혹은 인덱스)와 값(value)로 이루어져 있기 때문

 

배열의 장점

위에서 말했듯이 배열은 인덱스를 가지고 있기 때문에 값(데이터)에 바로 접근이 가능하다.

이러한 장점은 자료구조의 크기가 크면 클수록 더 강력한 힘을 발휘한다.

또 다른 장점으로는 연속된 메모리 공간에 존재하기 때문에 관리가 수월하다는 점이 있다.

 

배열의 단점

배열의 단점은 삽입과 삭제가 어렵고, 크기가 가변이 아니라는 점이다.

배열에서 데이터의 삽입과 삭제는 해당 위치에서 작업 이후,

해당 원소 뒤의 모든 원소들에서 이동이 이루어지기 때문에 시간이 오래 걸린다.

또한 배열은 처음 생성할 때 그 크기를 선언하기 때문에 크기의 가변이 어렵다.

 

 

리스트

리스트란

리스트와 배열의 가장 큰 차이는 인덱스의 유무이다.

배열에서는 인덱스를 통해 빠르게 데이터의 조회가 가능하다.

그러나 이 인덱스 때문에 원소가 삭제 되어도 인덱스를 유지해야하기 때문에

해당 메모리를 유지해야 한다는 단점이 존재한다.

그렇기 때문에 초기에 적절한 크기의 배열을 선언하지 않으면

메모리의 낭비를 초래하게 된다.

리스트는 이런 메모리의 낭비를 줄이기 위해 인덱스를 포기하고

노드를 연결해 데이터를 적재하는 형태의 선형 자료구조이다.

불연속적인 메모리 공간에 원소와 다음 노드의 주소를 가진 노드가

계속해서 이어져 있어 선형의 형태를 유지하는 것이다.

리스트는 주로 원소의 삽입과 삭제가 빈번하거나,

자료의 검색이 빈번하지 않은 경우에 사용한다.

 

리스트는 노드들을 연결하여 만든 것으로

노드는 기본적으로 헤드와 테일의 형태로 이루어져 있다.

각 노드의 테일에는 다음 노드의 주소 정보를 저장하고 있어

데이터가 불연속적인 메모리 공간에 위치하고 있어도

꼬리에 꼬리를 물고 원하는 원소에 접근이 가능하다.

그렇기 때문에 크기가 고정되어 있지 않고 새로운 원소를 추가할 경우,

테일 노드에 새롭게 추가된 원소의 주소를 연결해주면 된다.

 

리스트에서의 시간 복잡도

삽입

-리스트의 맨 앞에 삽입: O(1)

-리스트의 중간에서 삽입: O(n)

삭제

-리스트의 맨 뒤에 삽입/삭제: O(1)

-리스트의 중간에서 삭제: O(n)

탐색: O(n)

※위와 같이 시간 복잡도가 되는 이유는 리스트는 인덱스 접근이 불가해서

리스트 처음부터 링크를 타고 순차적으로 탐색해야 하기 때문

 

리스트의 장점

리스트의 가장 큰 장점이라면 크기가 가변이라는 것이다.

원소의 추가와 삭제에 따라 크기가 동적으로 변하기 때문에

연속적으로 메모리를 할당할 필요가 없고,

사용한 메모리도 재사용이 가능하여 메모리의 낭비가 적다.

 

리스트의 단점

배열과 비교했을때 리스트의 단점은 색인이 불가능하다는 것이다.

그렇기 때문에 탐색이 순차적으로 이루어지며 그만큼 시간이 소요되는 것이다.

또한 색인이 불가능하기 때문에 발생하는 단점으로

별도의 주소를 저장하는 공간을 필요로 하기 때문에 추가적인 메모리가 필요한 점이 있다.

 

참고) 리스트의 다양한 종류

리스트는 링크된 형태에 따라 다음과 같이 종류를 나눌 수 있다.

-링크드 리스트(Single Linked List)

<Single Linked List>

-더블 링크드 리스트(Double Linked List)

<Double Linked List>

-순환 링크드 리스트(Circular Linked List)

<Circular Linked List>

-순환 더블 링크드 리스트(Doubly Circular Linked List)

<Doubly Circular Linked List>

 

 

시간복잡도	배열	연결 리스트
k번째 원소 접근	O(1)	O(k)
임의 위치 원소 추가 제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
오버헤드(추가 필요 공간)	-	O(N)