Linked List vs Array (@GeeksforGeeks)

자료 구조를 공부하고 나서, Linked List와 Array가 서로 비슷하게 느껴졌다.
GeeksforGeeks에 비교해 놓은 글이 있어서 번역해 둔다.
(다시 읽으려면 힘드니까.....ㅎㅎㅎㅎㅎㅎ)

참고로 '기울기'로 표현한 부분은 추가로 공부하고 작성한 부분이다.

원글 : GeeksforGeeks - Linked List vs Array

Array와 Linked List 모두 유사한 유형의 선형데이터* 를 저장하는데 사용된다.
그러나 Array, Linked List 모두 장점들과 단점들이 있다.

* 원문에는 "linear data of similar type"이라 쓰여져 있던 부분이다.
Linear data는 Linear(선형) 구조의 data라 이해했다.
Linear(선형) 구조는 데이터가 순차적으로 나열된 구조로, 전후 관계가 1:1로 연결되어 있다.
Stack, Queue, Array, Linked List 모두 Linear 구조이다.
Tree, Graph는 1:n, n:m으로 연결된 비선형 구조이다

Key Differences Between Array and Linked List

• 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(메모리 활용도)이 효율적이다.

Following are the points in favor of Linked Lists.

1. Array의 사이즈는 고정된다.

   • 그래서 사전에 저장할 수 있는 데이터의 상한선(upper limit)을 알아야한다.
   • 또 사용여부와 상관없이 할당된 메모리의 상한선은 같다.
   • 실제로 상한선에 도달하는 건 드물다.

2. 새로운 데이터를 Array에 넣는 것은 비용이 많이 든다.
   (원문에 expensive로 표현 되어있는데,, '비싸다' 라는 표현이 맞나?)
   왜냐하면 새로운 데이터를 위해 room을 만들고,
   기존 요소를 이동하기 위해서 room을 만들어야 하기 때문이다.

   • 예를 들어, 정렬된 id 리스트가 담긴 "Array id"를 가정하자.
     id[] = [1000, 1010, 1050, 2000, 2040, …..]. 만약 우리가 새로운 ID 1005를 넣고 싶고, 순서를 유지하고 싶다면,
     "id 1000"을 포함하여 "id 1000" 뒤의 모든 아이디를 이동시켜야 한다.
     
   • 특별한 기술이 사용되지 않는다면 삭제 역시 비싸다.
     예를 들어, "id 1010"를 삭제하고 싶다면, "id 1010" 뒤의 아이디를 이동해야한다.

그래서 Linked List는 Array와 다른 2가지 이점이 있다.

1. 유동적인 size (Dynamic size)
2. 추가/삭제의 용이성 (Ease of insertion/deletion)

Linked list는 다음과 같은 단점이 있다.

1. Random access는 허용되지 않는다. 첫번째 node 부터 순차적으로 찾아야한다.
   그래서 binary Search는 Linked List와 함께 사용하지 않는다.
2. pointer를 위한 여분의 memory 공간이 list의 각 데이터와 함께 필요하다.
   (이전/뒤의 Node 정보를 알려주는 pointer를 저장하기 위한 별도 공간이 필요하다.)
3. Array는 cache locality가 뛰어나서 성능적인 측면에서 큰 차이점이 발생할 수 있다*.

* 이 부분에 대한 추가 설명은 stackoverflow에 설명되어있다.
내가 이해한 바로는 데이터가 저장될 때 Array는 Memory 블록이 연속적인데,
Linked Lists은 연속적인 Memory일 필요가 없어서 Memory 블록이 띄엄띄엄(?) 있다.
즉, 데이터를 찾아갈 때 시간이 더 걸린다는 얘기 아닐까?
(위에서 'key difference'로 정리한 'store' 부분 이라고 생각한다.)
stackoverflow 글을 꼭 확인하세요!
*출처: Why does cache locality matter for array performance?

Linked List vs Array ??

Insertion/Deletion이 자주 발생한다면 Linekd List,
Search를 하는 경우가 많다면 Array가 더 유리해보인다.

참고

• Linked List vs Array
• 선형구조와 비선형구조
• 알고리즘, 자료구조 개요
• 런타임(Runtime)과 컴파일타임(Compile Time)