[1주차] 배열과 리스트의 차이

 

리스트는 선형적으로(순서가 존재한다는 뜻) 값들을 가지고 있는 자료구조이며,

1) 배열(Array)과 2)연결 리스트(Linked list)로 나뉜다. 

출처: https://roi-data.com/

배열이란?

- 선형 자료구조형

- 하나의 변수에 여러 정보 담을 수 있음.

- 반복문과 결합하여 효율적으로 데이터 처리 가능

- 같은 자료형으로만 담을 수 있음.

- 연속된 메모리 공간에 순차적으로 저장 -> 배열의 논리적 순서(인덱스)와 원소값의 물리적인 순서(메모리 주소)가 동일.

 

어떨 때, 배열을 사용?

1) 데이터의 개수가 정해져 있는 경우

2) 데이터의 수정이 적은 경우

3) 데이터의 검색이 빈번한 경우

 

배열에서의 시간 복잡도

삽입/ 삭제

맨 앞에서 삽입/ 삭제: O(n) -> 해당 위치 이후의 모든 요소를 한자리씩 왼쪽으로 이동시켜야 함.

맨 뒤에서 삽입/ 삭제: O(1) -> 상수시간이 걸림. 크기를 동적으로 조절할 필요가 없음.

중간에서 삽입/삭제: O(n) -> 해당 위치 이후의 모든 요소를 한 자리씩 왼쪽으로 이동시켜야 함.

탐색

O(1)

 

배열의 장점

1) 값에 빠른 접근 가능: 인덱스를 가지고 있기때문에 값(데이터)에 바로 접근가능

2) 관리가 수월: 연속된 메모리 공간에 존재하기 때문

 

배열의 단점

1) 삽입과 삭제가 어렵다. -> 데이터의 삽입과 삭제는 해당 위치에서 작업 이후, 해당 원소 뒤의 모든 원소들에서 이동이 이루어지기 때문에 시간이 오래 걸린다.

2) 배열의 크기는 불가변이다.

 

연결 리스트

출처:  https://roi-data.com/

 

연결 리스트란?

- 리스트는 배열의 메모리 낭비를 줄이기 위해, 인덱스를 포기하고, 노드에 연결해 데이터를 적재하는 형태의 선형 자료구조

- 불연속적인 메모리 공간에 원소와 다름 노드의 주소를 가진 노드가 계속해서 이어져 있어, 선형의 형태를 유지

- 노드들을 연결해서 만든 것

- 헤드와 테일의 형태로 이루어져 있음.

- 각 노드의 테일에는 다음 노드의 주소 정보를 저장하고 있거, 데이터가 불연속적인 메모리 공간에 위치하고 있어도 꼬리에 꼬리는 물어 원하는 원소에 접근이 가능

- 크기가 고정되어 있지 않고, 새로운 원소를 추가할 경우, 테일 노드에 새롭게 추가된 원소의 주소를 연결해주면 된다.

- 포인터(pointer)를 통해 데이터를 연결

 

기존 배열의 문제점과 리스트의 장점

배열에서는 인덱스를 통해, 빠르게 데이터의 조회가 가능했지만/

인덱스때문에 원소가 삭제 되어도 인덱스를 유지해야했다. 따라서, 해당 메모리를 유지해야 한다는 단점이 있다. 그래서, 초기에 적절한 배열을 선언하지 않으면 메모리 낭비를 초래한다. -> 리스트는 메모리 낭비 없음.

 

어떨 때, 연결 리스트를 사용?

1) 원소의 삽입과 삭제가 빈번한 경우

2) 자료의 검색이 빈번하지 않은 경우

 

연결 리스트에서의 시간 복잡도

삽입/ 삭제

맨 앞에서 삽입/ 삭제: O(1)

맨 뒤에서 삽입/ 삭제: O(n) -> 끝까지 순회해야 함으로 선형 시간이 걸림.

중간에서 삽입/삭제: O(1) (특정 노드의 바로 뒤에서 삭제할 경우) 또는 O(n) (특정 노드의 위치를 찾아야 할 경우)

탐색

O(n) -> 모든 노드를 순회해야 원하는 요소를 찾을 수 있기 때문에,

 

리스트의 장점

- 크기가 가변

- 원소의 추가와 삭제에 따라 크기가 동적으로 변하기에 연속적으로 메모리 할당할 필요도 없고, 사용한 메모리도 재사용이 가능해서 메모리의 낭비가 적다.

 

- 배열과 비교해서 장점:

리스트의 장점은 중간에서의 요소 삽입 및 삭제에 있으며, 이러한 작업을 더 효율적으로 수행할 수 있다.

리스트와 배열에서 중간 이외의 위치에서의 삽입과 삭제 작업은 동일한 시간 복잡도를 가진다.

 

리스트의 단점

- 배열과 비교해서 단점:

배열과 달리 색인이 불가능하므로, 탐색이 순차적으로 이루어지며 그만큼 시간이 소요된다.

또한, 색인이 불가능해서, 별도의 주소를 저장하는 공간을 필요로 하기 때문에 추가적인 메모리가 필요하다.

 

연결 리스트의 종류

연결리스트 유형 (출처: faceprep)

 

 

한눈의 정리

구분	배열 (리스트)	연결 리스트
데이터 접근 방법	인덱스를 활용해 빠르게 접근 가능. O(1)	처음부터 순차적으로 탐색해야 함. O(n)
데이터의 추가/삭제	다른 데이터를 이동시켜야 함.	노드의 연결만 변경하면 됨.
메모리 사용량	고정된 크기로 미리 할당	필요한 만큼 동적으로 할당 가능
속도	구현이 상대적으로 쉬움	구현이 복잡함
데이터 탐색	O(1)	O(n)
앞에서 데이터 삽입/삭제	O(n)	O(1)
중간에서 데이터 삽입/삭제	O(n)	O(n)
뒤에서 데이터 삽입/삭제	O(1)	O(1)

 

참고:

https://bigsong.tistory.com/31

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

https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-3-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%E2%91%A2-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%9E%80-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EC%A0%95%EC%A0%81%C2%B7%EB%8F%99%EC%A0%81-%EA%B5%AC%ED%98%84

[자료구조] 3. 리스트-③: 연결 리스트란? / 리스트의 정적·동적 구현