[자료구조] 1. Array / Linked List

1. Array / Linked List

둘 다 데이터를 저장하는 선형 자료구조인데 그 목적과 장단점이 다르기 때문에 어떤 걸 사용하느냐에 따라 프로그램의 성능이 달라진다.

1) Array (배열)

특징

• 인덱스-원소값( index,value )의 쌍으로 구성
• 같은 타입의 데이터를 나열한 선형 자료구조 (sequence container)
• 데이터의 논리적 순서와 물리적 주소가 일치하며 항목을 연속된 메모리 공간에 순차적으로 저장
• 배열의 크기는 고정. 선언할 때에 배열의 크기를 정하고, 변경할 수 없다.
• Complie time에 연속된 메모리 주소를 할당받는다. (Stack 영역에 정적 메모리 할당)

시간 복잡도

• 배열의 맨 앞에 삽입/삭제하는 경우 : O(n)
• 배열의 중간에 삽입/삭제하는 경우 : O(n)
• 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
• 탐색(인덱스로 해당 원소에 바로 접근 가능): O(1)

삭제 또는 삽입, 배열의 어느 원소를 삭제하면 배열의 연속적인 특징이 깨져 빈 공간이 생긴다. 따라서 해당 원소에 접근하는 비용(O(1))에 추가로 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 하는 비용(cost)이 발생해서 시간 복잡도는 O(n)가 된다. 그렇기 때문에 Array 자료구조에서 삭제 기능에 대한 time complexity 의 worst case 는 O(n)이 된다. 삽입도 마찬가지로 새로운 원소를 추가할 때 모든 원소들의 인덱스를 1 씩 shift 해야 하므로 O(n)의 시간이 필요하다.

장점

• Random Access 인덱스를 가지고 있어 원소로 바로 접근 가능 = 시간복잡도 O(1)
• 연속된 메모리 공간에 존재하기 때문에 정적인 자료는 관리하기가 편하다.

단점

• 삽입과 삭제가 어렵고 오래 걸린다.
• 원소 삽입 혹은 삭제 시, 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야 한다.(연산량 증가)
• 배열은 처음 생성할 때 크기를 설정하고 크기를 바꿀 수 없다.
• 배열의 크기를 프로그램 실행전에 최대크기로 선언해야 함 (런타임에 확장 불가)
• 크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 선언한 뒤 값을 복사해야 함.
• 연속된 메모리라서 공간 낭비가 발생할 수 있다.
• 중간에 데이터가 삭제되면 공간 낭비가 발생할 수 있음. 또, 선언한 크기보다 적게 사용하면 낭비가 발생함.

사용

• 순차 데이터 저장할 때 (ex. 주식, 대회 결과, 날씨 등)
• 다차원 데이터를 다룰 때 (ex. 배열 안의 배열)
• 특정 요소를 빠르게 읽어야할 때 (ex. index로 바로 불러오는 경우)
• 데이터 사이즈가 (거의) 바뀌지 않을 때
• 데이터가 자주 삭제 되거나 추가되지 않을 때

 

---

 

2) Linked List (연결 리스트)

연결리스트(Linked List)

• 선언할 때 크기를 미리 정할 필요가 없으며 고정되어있지 않다.
• 새로운 노드가 추가되면 runtime에 추가 할당 가능하다. (Heap 영역에 동적 메모리 할당)
• 논리적 순서와 데이터의 물리적 주소가 다르다.
• 연결리스트의 노드는 저장된 데이터 값과 다음 데이터가 있는 위치(메모리 주소)를 가지고 있다.
• 인덱스로 데이터에 접근이 불가능하고 연결된 링크를 따라 데이터를 탐색하는 순차 접근(sequential access) 방식을 사용한다. = 시간 복잡도 O(n)
• 데이터 삽입과 삭제가 용이하다. 논리적 주소만 바꿔주면 된다. = 시간복잡도 O(1)
• (그러나, 삽입할 위치를 찾아야한다면 O(N)의 시간 복잡도를 가진다.)

 

---

 

 

• 저장할 데이터 개수가 정해져 있고 리스트 중간에 데이터를 삽입, 삭제하는 작업이 많지 않으며 인덱스를 이용한 빠른 검색이 필요할 경우에는 배열을 사용하는게 효율적
• 저장할 데이터 개수가 정해져 있지 않고 리스트 중간에 데이터를 삽입하거나 삭제하는 작업이 많고 삽입, 삭제에 비해 특정 위치의 데이터를 검색하는 작업이 많지 않을 경우 연결 리스트를 사용하는게 효율적

= 목적에 따라 선택하는 것이 중요하다