Linked List vs Array, 정적할당 vs 동적할당

탐색

• Array는 index를 통해 요소에 직접 접근이 가능하다. (Random Access, O(1))
• Linked List는 처음부터 타겟을 찾을 때까지 순차적으로 검색해야 한다. (Sequential Access, O(n))

크기

• Array는 크기가 제한되어 있다.
• Linked List는 크기 제한 없이 새로운 요소를 추가 가능하다.

삽입

• Array는 요소들이 실제로 메모리에서도 인접하고 연속적이게 할당되어 있다.
• Linked List는 메모리에 연속적으로 할당되는 것이 아닌, 빈 메모리에 할당된다.
• 삽입 시 Array는 해당 index를 탐색한 뒤 ( O(1) ) 뒤의 원소들을 모두 한 칸씩 뒤로 shift 해줘야 한다. -> 전체: O(n)
• 삽입 시 Linked List는 해당 index를 탐색한 뒤 ( O(n) ) 이전의 노드가 새로운 원소를 가리키고, 새로운 원소가 다음 노드를 가리키도록 하면 된다.(O(1)) -> 전체: O(n)

삭제

• 삭제 시 Array는 해당 index를 탐색한 뒤 ( O(1) ) 원소를 삭제하고 뒤의 원소들을 모두 한 칸씩 앞으로 shift 해줘야 한다. -> 전체: O(n)
• 삽입 시 Linked List는 해당 index를 탐색한 뒤 ( O(n) ) 이전의 노드가 삭제된 원소의 다음 원소를 가리키도록 하면 된다.(O(1)) -> 전체: O(n)

시간복잡도

• 탐색의 경우 Array는 O(1), Linked List는 O(n)을 가진다.
• Linked List가 삽입/삭제 자체의 시간복잡도는 O(1)이지만, 이를 위한 탐색의 시간복잡도가 O(n)이기 때문에 Array와 Linked List 모두 O(n)을 가진다.

메모리 할당

• Array는 선언될 때 메모리에 할당이 된다. 즉 Compile Time에 할당이 된다. (Static Memory Allocation)
• Linked List는 새로운 노드가 추가될 때 메모리에 할당이 된다. 즉 Run Time에 할당이 된다. (Dynamic Memory Allocation)
• Array는 Stack에, LinkedList는 Heap에 메모리 할당이 이루어진다. (정적 vs 동적)
• 그러나 Array의 경우에도 new, malloc 등을 통해 런타임에 동적 할당이 가능하다. 이 때는 힙을 사용한다.
• 2차원, 3차원 Array의 경우에도 실제 메모리에는 1차원으로 연속적으로 메모리가 할당이 된다. 이는 컴퓨터의 메모리 공간이 1차원으로 이루어져있기 때문이다.

정적할당 vs 동적할당

• 정적 할당은 컴파일 타임에 메모리 공간을 할당받는다.
• 정적 할당은 메모리 누수의 걱정이 없다. 그러나 컴파일 후 런타임에는 그 크기를 변경할 수 없다.
• 동적 할당은 런타임에 메모리 공간을 할당받는다.
• 런타임에 크기 변경이 가능하지만, 메모리 누수의 위험이 있다. 직접 메모리 해제를 해줘야한다.

메모리 누수란?

컴퓨터 프로그램이 필요하지 않은 메모리를 계속 점유하는 현상

Linked List의 종류

• 단일 연결 리스트: 각 노드의 포인터가 다음 노드를 가리킨다.
• 이중 연결 리스트: 각 노드의 포인터가 다음 노드와 이전 노드를 가리킨다.
• 원형 연결 리스트: 각 노드의 포인터가 다음 노드를 가리키며, 마지막 노드의 포인터가 처음 노드를 가리킨다. 만약 이전 노드를 가리키는 포인터도 있다면 이중 원형 연결 리스트가 된다.