[개발지식] Array vs LinkedList

Array(배열)

• 논리적 저장순서와 물리적 저장 순서가 일치한다.
• 인덱스로 해당 원소에 접근이 가능하다.
• 인덱스만 알고 있다면 시간 복잡도 O(1)만에 해당 원소로 접근할 수 있다.
• 즉, Random Access가 가능하다.
• 배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 가진 원소들을 옮겨줘야(Shift) 하기 때문에 시간 복잡도 O(n)이 걸린다.
• 삽입의 경우, 새로운 원소를 추가하고 모든 원소들의 인덱스를 1씩 Shift 해줘야 하므로 시간 복잡도 O(n)이 걸린다.
• 제한적인 크기를 갖는다.

즉, 삭제 또는 삽입 과정에서 해당 원소에 접근하여 작업을 완료한 뒤 Shift를 해줘야 하는 cost가 발생해 O(n)의 시간복잡도를 갖는다.

LinkedList

• 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조를 갖는다.

• 삽입과 삭제의 경우 LinkedList가 Array보다 속도가 빠르다고 하지만 엄밀히 말하면 경우에 따라 다르다.
  - 삽입
  LinkedList는 어느 곳에 삽입하던지 O(n)의 시간복잡도를 갖는다. (만약, 중간 삽입이 없다면 즉 맨 앞과 맨 뒤에만 삽입한다면 -> 시간 복잡도 : O(1))
  - 삭제
  어느 곳에 삽입하던지 O(n)의 시간 복잡도를 갖는다. (만약, 중간 삭제가 없고 맨 앞과 뒤에서만 삭제한다면 -> 시간 복잡도 : O(1))

• 원하는 값을 찾기 위해서 최소 한 번은 리스트를 순회하여야 하므로 O(n)의 시간 복잡도를 갖는다.

• 트리의 근간이 되는 자료구조이다.

LinkedList 역시 삽입과 삭제를 위해서 해당 노드를 찾아가는 동안 O(n)의 시간 복잡도를 갖는다. 추가적으로 데이터를 삽입 / 삭제하기 위한 시간 복잡도까지 계산하면 결국 O(n)의 시간 복잡도를 갖는 셈이다.

Array VS LinkedList

Data type

• Array는 비슷한 유형의 데이터 집합을 저장하는 자료 구조이다.
• Linked List는 순서가 없이 연결된 데이터 집합(Node)을 저장하는
  참조형(non-primitive) 자료구조이다.

Seach

• Array는 index로 데이터의 위치를 나타낸다.
  만약 4번째 데이터를 알고 싶다면, Array 변수를 index를 넣은 대괄호([])와 함께 입력하면 된다.
• Linked List는 head부터 시작해서 4번째 데이터를 얻을 때까지 찾아야 한다.
• 즉, 데이터를 찾는 것은 Array가 빠르고, Linked List는 선형 시간(linear time)이 걸리기 때문에 조금 느리다.

Insertion, Deletion

• Array에서 추가(Insertion)와 삭제(Deletion)는 많은 시간이 소요된다.
  (ex, index 0번째 데이터가 삭제되면 그 뒤의 모든 데이터가 앞으로 이동해야된다.)
• 반면, Linked List의 추가(Insertion)와 삭제(Deletion)는 빠르다.
  (ex, Node를 삭제 할 때, 삭제 Node의 '다음' 정보를 이전 Node의 '다음' 정보로 연결한다.

Size

• Array의 Size는 고정되어 있다.
• Linked List는 유동적이고 유연하며, 그들의 Size를 확장하고 축소할 수 있다.
  (Array도 Size는 바꿀 수 있지만, 처음에 만들어질 때 Size가 고정되는 반면,
  Linked List는 Size가 고정 되지 않고, 바로 추가/삭제된다.)

Memory

• Array는 Compile time(컴파일 타임) 동안 할당된다.
• Linked List는 실행 or Runtime(런타임) 동안 할당된다.
  * Compile time : 개발자가 작성한 소스 코드가 기계어 코드로 변환되어 실행 가능한 프로그램이 되는 과정
  * 런타임: 컴파일 과정을 마친 응용프로그램이 사용자에 의해 실행되어 지는 '때(Time)'

Store

• Arrary에서는 연속적으로(consecutively) 저장된다.
• Linked List에서는 랜덤하게(randomly) 저장된다.

Requirement of memory

• Array는 Actual Data가 Index로 저장되어 메모리 요구사항이 적다.
• Linked List는 이전과 다음 데이터의 참조를 위해 더 많은 메모리가 필요하다.

Memory utilization

• Array는 Memory utilization(메모리 활용도)이 비효율적이다.
  (ex, 빈 배열의 4번째 index에 데이터를 바로 저장하면, 0 ~ 3번째는 undefined가 저장된다.
  즉 0~3번째는 빈 상태로 저장되므로 메모리 활동도가 좋지 않다.)
• Linked Lists는 Memory utilization(메모리 활용도)이 효율적이다.

---

참고 링크
https://wooono.tistory.com/281
https://www.javatpoint.com/ds-array-vs-linked-list
https://velog.io/@thms200/Linked-List-vs-Array-GeeksforGeeks
https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/