배열(Array) vs 연결리스트(Linked List) | 차이점 비교 및 사용 이유

1. 배열 (Array)

연관된 데이터를 하나의 변수에 그룹핑해서 관리하기 위한 자료구조

 

배열은 elements로 이루어져 있으며, element는 value와 index로 이루어져있다.

순차적으로 저장되어 메모리 주소가 1씩 차이나는 것을 볼 수 있다. 이와 같은 특징 덕분에 index를 사용할 수 있다.

즉, 배열의 장점은 시작 주소만 알면 index를 활용해 쉽게 탐색이 가능하다는 것이다.

 

✨특징

• 정적(static)인 자료구조
  • 배열을 선언할 때 크기와 데이터 타입을 지정 (e.g. int arr[10] , String arr[5])
  • 크기 수정 불가
  • 배열 크기 이상의 데이터 저장 불가
  ⇒ 최대 사이즈를 알 수 없을 때는 사용하기에 부적합
• 처음에 정한 크기만큼 연속된 메모리 주소를 할당
  • 메모리상에 연속적으로 저장 = 논리적 저장 순서와 물리적 저장 순서가 일치
  ⇒ index로 해당 원소(element)에 임의 접근(random access)가능하다는 장점
• ⇒ 데이터 삽입/삭제가 비효율적이라는 단점

✨시간 복잡도

• 데이터 탐색
  • O(1): 접근하고자 하는 인덱스를 알고있는 경우
    • 임의 접근 방식을 사용하기 때문에 처음부터 찾을 필요가 없다.
  • O(n): 인덱스를 알지 못해 순차적으로 탐색하는 경우
• 데이터 삽입/삭제
  • 배열의 끝에 삽입 및 삭제: O(1)
  • 배열의 처음 또는 중간에 삽입 및 삭제: O(n)
    • 삽입 지점 이후의 인덱스를 갖는 모든 원소들을 1씩 shift해줘야 하는 비용 발생

 

 

---

 

2. 연결리스트 (Linked List)

 

여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조

• 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

 

* 연결리스트 노드를 구조체로 간단하게 구현하면 이럴 것이다.

// A linked list node 
typedef struct Node 
{ 
  int data; 
  struct Node *next; 
};

- 구조체 Node 는 멤버변수 data, *next 를 갖는다.

- data 멤버변수는 저장할 데이터의 값을 담는 변수이다.

- *next 멤버변수는 다음 노드의 Node 구조체를 가리키는 포인터이다.

 

✨특징

• 동적(dynamic)인 자료구조
  • 크기를 미리 정할 필요가 없다.
• 저장되는 메모리 위치가 연속적이지 X = 논리적 저장 순서와 물리적 저장 순서가 불일치
• ⇒ 순차 접근(sequential access) 방식으로 데이터를 탐색
• 각각의 원소들은 자기 자신 다음 원소가 어떤 원소인지만을 기억한다.
• ⇒ **데이터 삽입, 삭제가 용이 (**이전 노드와 다음 노드가 가리켰던 주소값만 수정하여 연결해주면 되기 때문)

 

✨시간 복잡도

• 데이터 탐색 : O(n)
  • 순차 접근 방식을 사용하기 때문에 어떤 한 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야한다.
• 데이터 삽입/삭제
  • 연결리스트의 처음에 삽입/삭제: O(1)
  • 연결리스트의 중간에 삽입/삭제: O(n)
    • 데이터를 삽입/삭제하는 것 자체는 O(1) 시간복잡도를 갖지만, 삽입/삭제하려는 데이터의 위치를 순차적으로 탐색하면서 해당 위치까지 가야하기 때문에 O(n)의 시간복잡도가 발생
  • 연결 리스트의 끝에 삽입/삭제 :
    • 끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
    • 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) (탐색시간 소요)

 

2-1) 연결리스트의 연산 과정

삽입

1. 노드를 생성하고, 삽입하려는 위치를 찾는다.

1. 삽입할 노드를 NewNode라고 하면, NewNode가 그 다음 노드를 가리키게 한다.

NewNode.next -> RightNode

1. 새로 삽입한 노드의 이전 노드가 새로운 노드를 가리키게 한다.

LeftNode.next -> NewNode

 

삭제

1. 탐색을 통해 삭제하고자 하는 노드(TargetNode)를 찾는다.
2. TargetNode의 왼쪽 노드가 TargetNode의 오른쪽 노드를 가리키게 한다.LeftNode.next -> TargetNode.next
3. TargetNode가 RightNode를 가리키지 않게 한다 TargetNode.next -> NULL

 

2-2) 이중 연결 리스트 (Doubly Linked List)

• 이중 연결 리스트는 위에서 언급한 연결 리스트와 다르게 전/후로 탐색이 가능한 구조이다.
• 즉, 단순 연결 리스트의 노드는 데이터와 다음 노드의 주소를 저장한다면, 이중 연결 리스트의 노드는 데이터, 이전 노드의 주소와 다음 노드의 주소를 저장하게 된다.

• 장점 : 단순 연결 리스트에서는 최악의 경우 n번의 탐색을 해야하지만, 이중 연결 리스트에서는 얻고자 하는 데이터의 위치가 tail에 가깝다면 tail에서부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있다.

 

2-3) 원형 연결 리스트 (Circular Linked List)

• 원형 연결 리스트는 단순 연결 리스트의 마지막 노드가 null을 가리키는 게 아닌, 처음 노드를 가리키는 구조이다.
• 즉, head에서부터 순회를 반복적으로 진행하다보면 다시 처음으로 돌아오는 구조이다.
• 이중 연결 리스트도 마지막 노드가 처음 노드를 가리키는 구조가 되면, 이를 이중 원형 연결 리스트라고 한다.

 

 

---

 

3. 배열(Array) vs. 연결리스트(LinkedList)

	배열(Array)	연결리스트(Linked List)
크기	정적 (선언할 때 크기 고정, 변경 불가)	동적 (데이터를 삽입할 때마다 증가)
물리적 주소	순차적 :논리적 저장 순서 = 물리적 저장 순서	랜덤 :논리적 저장 순서 ≠ 물리적 저장 순서
원소 접근	임의 접근(Random Access)	순차 접근(Sequential Access)
탐색	index 만 안다면 O(1)	O(n)
삽입/삭제	1. 끝에서 삽입/삭제: O(1) 인덱스로 접근 후 삽입 및 삭제 O(1) 2. 처음과 중간에서 삽입/삭제: O(n) 인덱스로 접근 후 삽입 및 삭제 O(1) + 1씩 shift 추가 작업 O(n) = O(n)	1. 맨 앞/끝에서 삽입/삭제: O(1) 삽입/삭제 O(1) 2. 중간에 삽입/삭제: O(n 삽입하려는 위치 접근 O(n) + 삽입/삭제 O(1) = O(n)
종류	single dimensional, two dimensional, multidimensional	Linear(Singly), Doubly, Circular linked list
메모리 할당	- Static Memory Allocation (Array 가 선언되자 마자 Compile time 에 할당) - Stack 영역에 memory 할당	- Dynamic Memory Allocation (새로운 node 가 추가될 때 runtime 에 할당) - Heap 영역에 memory 할당
장점	1. 탐색 속도 빠름	1. 동적 크기 2. 삽입/삭제 용이
단점	1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함 2. 새로운 요소를 삽입하는 것은 비용이 많이 듦 (공간을 만들고, 기존 요소 전부 이동)	1. 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 (이진 검색 수행 불가능) 2. 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요
결론	빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때 사용	삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때 사용
PS 팁	일반적인 알고리즘 문제를 풀때는 Array가 훨씬 빠르고 편리 → 대부분의 알고리즘 문제는 메모리 공간의 범위를 파악할 수 있도록, N 의 크기가 주어지기 때문에 배열의 크기를 MAX로 초반에 잡는다면 Array가 훨씬 빠르고 편리	• Linked List는 요소를 삽입, 삭제할 때마다 메모리의 할당,해제가 발생 • 이런 작업은 시간복잡도에 포함되지는 않지만, 시스템 콜(System Call)을 사용하는 구문은 시간 소요가 꽤 걸림

 

 

 

---

4. (Optional) ArrayList vs. Linked List

1. ArrayList

• 내부적으로 데이터를 배열에서 관리하며 데이터의 추가, 삭제를 위해서 임시 배열을 생성해 데이터를 복사하는 방법을 사용한다.
• 대량의 자료를 추가/삭제 하는 경우 그만큼 데이터의 복사가 많이 일어나게 되어 성능 저하가 발생
• 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 존재해야 한다.
• 반면 인덱스를 가지고 있어서 한 번에 참조가 가능해 데이터 검색에 유리하다.

=> ArrayList는 삽입과 삭제를 할 일이 없거나 배열의 끝에서만 하게 될 경우 유용하게 쓰일 수 있다. 원소에 대해 빠르게 접근할 수 있을 뿐만 아니라, 원소들이 메모리에 연속으로 배치해 있어 CPU 캐시 효율도 더욱 높다.

 

 

2.LinkedList

• 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있으면 된다.
• ArrayList와 달리 데이터의 추가, 삭제시 불필요한 데이터의 복사가 없어 데이터의 추가, 삭제시에 유리하다.
• 반면, 데이터 검색 시에는 처음부터 노드를 순회하기 때문에 성능상 불리하다.

 

 

3. 데이터의 검색,삽입,삭제시 성능 비교

검색

• ArrayList : 인덱스 기반이기 때문에 O(1)의 시간복잡도를 갖는다.
• LinkedList : 검색 시 모든 요소를 순차적으로 탐색해야 하기 때문에 O(N)의 시간 복잡도를 갖는다.

삽입,삭제

• ArrayList : 삽입,삭제 이후 다른 데이터를 복사해야 하기 때문에 O(N)의 시간복잡도를 갖는다.
• LinkedList : 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문에 삽입, 삭제 시에 O(1)의 시간 복잡도를 갖는다. 하지만 이 부분도 경우에 따라 다르다.

 

---

참고 자료

• https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list
• https://gyoogle.dev/blog/computer-science/data-structure/Array.html
• https://hongcoding.tistory.com/74
• https://letitkang.tistory.com/111
• https://wooono.tistory.com/281