[CS] Array vs LinkedList

📚 본 포스팅은 CS 완전정복 강의를 수강하고 적는 복습 포스팅입니다.

1. Array

연관된 데이터를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조

여기서 중요한거는!!

1. 메모리상에 연속적으로
2. 미리 할당된 데이터만큼

이라는 두가지 포인트가 중요하다.

Array는

• 고정된 자장공간
• 순차적 데이터 저장

이라는 특징을 가지고 있음

컴퓨터의 메모리의 일정 부분을 array 요소 하나의 크기로 할당하고, 그 시점부터 연속적으로 array의 크기만큼 할당한다.

Array Operation들의 Time Complexity

1. 조회 -> O(1) random Access
   특정 인덱스의 값 조회는 계산으로 바로 접근 가능하기 때문에 다음과 같은 시간복잡도를 가진다.
   ex) array의 한 요소에 메모리 4개가 할당되었고 4번째 index의 값을 알고싶다면?
   첫 index + 4(메모리크기) x 3(index)
   이런식으로 계산해서 접근 후 조회한다.

2. 마지막 인덱스 데이터 추가/삭제 (append(), delete()) -> O(1)
   그냥 마지막 메모리에 데이터를 넣기만 하면 되기 때문이다.

3. 삽입 / 삭제 -> O(n)
   삭제 / 삽입을 한 후 남은 데이터들을 한 칸씩 옮겨줘야하기 때문에 n개의 배열이라면 O(n)의 시간복잡도가 발생하게 된다.

4. 탐색 -> O(n)
   일일이 방문해서 확인하기 때문에 O(n)의 시간복잡도가 발생하게 된다.

다음과 같은 특징을 바탕으로 장점과 단점이 있다.
장점: 조회랑 데이터 추가의 속도가 빠르다
단점: 선언시에 크기를 미리 정해야하고 이에 따라 메모리 낭비나 추가적 overhead와 같은 문제가 발생할 수 있다.

2. Dynamic Array

Array의 fixed size라는 한계점을 보완하기 위해 고안된 Array.
저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절해 데이터를 저장하는 자료구조이다.

중요하게 볼 것은 두가지

1. resize 방식
2. 데이터를 추가할 때 시간복잡도

resize 방식
기존에 할당된 메모리 이상으로 데이터가 들어온다면?
기존의 메모리보다 크게 메모리를 할당한 배열을 선언한 후 그 배열로 모든 데이터를 옮긴다.
대표적으로는 기존 Array Size의 2배를 할당하는 Doubling 방법이 있다.

Doubling (더블링)
기존 배열 사이즈보다 2배 큰 배열을 선언함

큰 배열을 선언하고 기존의 배열의 모든 데이터를 옮겨야 하기 때문에 O(n)의 시간복잡도를 가진다.

데이터를 추가할 때의 시간복잡도
Dynamic Array도 Array이기 때문에 결국 데이터를 추가할때는 O(1)의 시간복잡도를 가진다.
하지만 resize의 시간복잡도는 O(n)
그렇다면 데이터 추가의 시간복잡도는?

결론은 O(1) 이다.
데이터를 추가할 때 resize가 일어나는 경우는 아주 가끔 발생한다. 따라서 주로 O(1)의 시간 복잡도를 가지게 되는것.

이를 amortized O(1)이라고 한다.
아주 가끔 발생하는 O(n)의 시간복잡도를 자주 발생하는 O(1)이 나눠가지면서 O(1)이 된다고 생각하면 된다. 바닷물에 식초를 빠뜨린다고 해서 바닷물이 셔지지는 않고 여전히 짠 그런거일려나..? ㅎ

Dynamic Array vs Linked List

Dynamic Array를 Linked List와 비교했을 때 장단점은 무엇일까?

장점
1. Dynamic Array가 Linked List에 비해 데이터 접근과 할당이 O(1)로 빠르다. index 접근법이 연산으로 이루어지기 때문 (random access).
2. 데이터를 맨 뒤에 추가/삭제가 O(1)로 상대적으로 빠르다.

단점
1. 맨 끝이 아닌 곳에 데이터를 삽입/삭제 할 때는 O(n)으로 느리다. 데이터들을 shift 하기 때문.
2. resize시 현저히 낮은 performance 발생. 데이터를 다 옮겨야 하기 때문.
3. 메모리공간을 resize 시에 넉넉히 할당받는데 이렇게 되면 사용하지 않고 남는 메모리 공간이 발생 할 수 있다.

3. Linked List

node 구조체로 이루어져 있는 자료구조. node에는 데이터값과 다음 node의 address가 저장되어 있다. 물리적 메모리 상에서는 비연속적으로 나타나지만 각각의 node가 다음 node의 address를 가리킴으로써 논리적 연속성을 가진 자료구조이다.

중요한 포인트

1. node
2. 물리적 메모리는 비연속적
3. 논리적 연속성

Linked List는 tree, graph 등 다른 자료구조에서 자주 사용되는 기본이다. 설명 포인트는 메모리상에서는 불연속적이지만 node의 address값을 가리키기 때문에 논리적 연속성을 보장한다.
또한 데이터가 추가되는 시점에 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용이 가능하다.
node에는 데이터 값과 다음 node의 address가 저장되어 있는데 마지막 node가 가리키는 address는 0x00000로 null값이다.

논리적 연속성

각 node들은 next address 정보를 가지고 있기 때문에 논리적 연속성을 가지고 있고 연결되어 있다. Array는 이와는 다르게 연속성을 위해 메모리에 순차적으로 저장된다. Linked List는 논리적 연속성으로 메모리에 순차적으로 저장될 필요가 없기 때문에 메모리 사용이 더 자유롭고 효율적이지만 각각의 데이터가 데이터값만 가지고 있는 것이 아니라 address도 추가로 저장되기 때문에 각 데이터가 차지하는 메모리는 더 크다.

데이터 삽입/삭제

Linked List에서 데이터의 삽입과 삭제는 둘다 node의 address 값만 변경해주면 된다.
삽입을 원하는 경우는 원하는 위치의 앞의 노드의 address를 삽입하는 data의 address로 변경해주면 되고 삭제를 원하는 경우는 삭제하는 노드의 앞의 노드의 address를 뒤의 address로 변경해주면 된다. 따라서 시간복잡도는 O(1)이 된다.

데이터 access (접근) / search

데이터 접근의 시간복잡도는 O(n)이다. Linked List는 데이터의 순차적 접근만이 가능하기 때문이다. n번째의 데이터가 알고 싶다면 처음부터 n까지의 address를 따라가야 한다. search도 같은 방식으로 작동한다.

4. Array vs Linked List?

Array는 메모리상에 데이터가 연속적으로 저장된다. Linked List는 연속적으로 저장되진 않지만 논리적 연속성을 띈다. 이에 따라 각 operation의 시간복잡도가 다르게 나타난다.

	Array	Linked List
조회	O(1)	O(n)
삽입/삭제	O(n)	O(1)

따라서 데이터의 갯수가 정해져있고 자주 조회한다면 Array를 사용하면 되고
데이터의 갯수를 예상할 수 없고 삽입/삭제가 자주 일어난다면 Linked List를 사용하면 된다.
주된 차이점은 메모리구조로 Array는 연속적, Linked List는 불연속적이라는 걸 외워두면 된다.

둘은 각각 메모리 활용도도 다르기 때문에 상황에 따라 뭐가 더 효율적인지 판단하면 된다.

조회

• Array: 즉시 접근 random access. O(1)
• Linked List: 순차 접근 sequential access. O(n)

삽입/삭제

• Array: 마지막인 경우 -> O(1) / 중간인 경우 -> O(n)
• Linked List: 주소값만 바꾸기 때문에 O(1)의 시간복잡도
  하지만 Linked List는 해당 index까지 가는 데에 O(n)의 시간복잡도를 가진다.

memory

• Array: fixed size라서 데이터가 저장되어 있지 않더라도 메모리를 차지하고 있을 수 있기 때문에 메모리 낭비가 발생 가능하다.
• Linked List: runtime 중에서도 size 늘리고 줄이기가 가능하기 때문에 initial size를 고민할 필요가 없고, 필요한 만큼만 memory allocation이 일어나기 때문에 메모리 낭비도 없다.
  하지만 Linked List는 address 저장 메모리도 함께 사용하기 때문에 Array보다 각 원소의 memory가 크다. 따라서 데이터의 수가 정해져있다면 메모리상에서는 Array가 더 효율이 좋다.

Linked List를 사용하는 상황

1. 삽입/삭제가 자주 발생
2. 조회 작업이 자주 발생하지 않음
3. 데이터의 양을 예측할 수 없을 때

Array를 사용하는 상황

1. 조회 작업을 자주 할 때
2. 데이터 갯수를 미리 아는 경우
3. 데이터 반복문을 통해 빠르게 순회할 때
4. 메모리를 적게 쓰는게 중요한 상황일 때

Array와 Linked List의 Memory Allocation은 언제 일어나며 메모리의 어느 영역에 할당되는가?

• Stack 영역 -> compile time에 메모리 크기 결정
• Heap 영역 -> runtime에 메모리 크기 결정

Array는 compile 단게에서 memory allocation
= Static Memory Allocation으로 Stack Memory 영역에 할당

Linked List는 runtime 단계에서 memory allocation
= Dynamic Memory Allocation으로 Heap Memory 영역에 할당