[알고리즘] 배열과 연결리스트의 차이? (Array vs Linked List)

배열과 연결리스트 정리

 

 

 

배열과 연결리스트 자료구조 알아보기!

 

---

연결 리스트(Linked List) 란?

• 링크드 리스트 라고도 한다.
• 메모리를 동적으로 사용가능하다.
• 데이터 재구성이 용이하다.
• 대용량 데이터 처리에 적합한 자료구조이다.
• 노드(Node)로 구성되어 있으며 노드 두개의 셀이 있는데 첫번째 셀에는 실 데이터가 있으며 두번째 셀에는 다음 노드의 시작 메모리 주소를 뜻하는 링크가 들어있다. (자료의 주소값으로 연결된 구조)
• 마지막 노드의 두번째 셀에는 Null값을 가진다. (마지막 노드이기 때문에 다음 노드의 링크가 없기떄문!)
• 노드가 서로 이웃하지 않기 때문에 각 노드의 위치를 바로 검색할 수 없다.(첫 노드부터 순차탐색 해야함)

 

배열이란?

• 배열은 크기가 고정적이다.
• 연속적인 메모리공간이 필요하기 때문에 최대 데이터 개수를 지정해야하는 제약사항이 있다.
• 인덱스를 사용하여 데이터를 접근하기 때문에 임의의 원소에 바로 접근이 가능하다. (랜덤엑세스가 빠름
• 배열 내에서 데이터 이동 및 재구성이 어렵다.
• 크기를 정한 후 모자른 경우 메모리를 추가로 할당하여 배열의 데이터를 복사하는 과정을 거친다.
•  

 

 

 

배열와 연결리스트의 차이 (검색 / 삽입 / 삭제)

* 검색 (배열 승)

배열은 인덱스(index)만 있다면 O(1)에 접근하며

연결리스트는 최소 한번은 리스트를 순회해야 하므로 O(n)에 접근한다.

 

 

* 삽입 (경우에 따라 다르지만 연결리스트 승)

만약 배열에 공간이 여유롭고 데이터를 맨 끝에 삽입한다면 삽입속도는 O(1) 이다.

하지만 이런 경우는 드물기에 연결리스트의 장점이 부각된다.

연결리스트는 어느 위치에 삽입해도 O(n)이다.

 

 

1. 0번째 인덱스에 요소를 삽입할 경우

연결리스트가 배열에 비해 막강한 장점을 갖는 경우이다.

배열은 이 경우에 뒤에있는 모든 데이터를 한 셀씩 우측으로 이동시켜야한다.

반면 연결 리스트는 이 경우 딱 한단계O(1) 만 걸린다.

 

2. 마지막 인덱스에 요소를 삽입할 경우

해당 경우에는

배열은 한단계O(1) 로 요소를 추가할 수 있는 반면

연결 리스트는 마지막 노드를 전부 검색O(n)한 후 + 삽입O(1)하는 단계가 진행되므로

배열이 훨씬 높은 효율성을 가지게 된다.

 

3. 중간에 요소를 삽입할 경우

해당 경우

배열과 연결리스트 모두 O(n)의 시간복잡도를 가지므로 평균적인 효율성을 가지게 된다.

 

 

 

* 삭제 (경우에 따라 다르지만 연결리스트 승)

 

1. 0번째 인덱스에 요소를 삭제할 경우

연결 리스트는 한단계 O(1) 로 삭제가 가능하다. 단순히 첫번째 노드가 두번째 노드를 가르키게 하면 되기 때문이다.

반면, 배열은 해당 경우에 나머지 데이터 모두 왼쪽으로 시프트해야 하므로 효율성은 O(n)이 된다.

 

2. 마지막 인덱스에 요소를 삭제할 경우

연결리스트의 경우 마지막 노드를 전부 검색O(n)한 후 + 삭제O(1)하는 단계가 진행로 진행된다.

앞서 언급한대로 연결리스트의 마지막 노드는 null값을 가지므로,

마지막 노드 삭제시 뒤에서 두번째 노드에 null을 가르키는 링크를 넣어주는 단계가 필요하다.

 

배열은 임의의 원소에 바로 접근이 가능하므로 마지막 요소를 바로 삭제O(1)할 수 있다.

 

 

3. 중간에 요소를 삽입할 경우

해당 경우

배열과 연결리스트 모두 O(n)의 시간복잡도를 가지므로 평균적인 효율성을 가지게 된다.

 

 

배열의

배열은 확보한 메모리 크기를 초과할 경우 크기에 맞는 새 메모리의 위치로 배열 전체를 이동하게 된다.

매번 모든 노드를 새로운 메모리 위치로 옮긴다면 배열에 노드를 추가하는 작업은 아주 느려지게 될것이다.

따라서 컴퓨터 메모리를 10의 크기만큼 요청해놓음으로 이를 해결할 수 있는데,

이럴 경우 미사용 메모리 공간을 낭비하게 된다는 단점이 있다.

 

 

데이터가 자주 추가되거나 가변적으로 자주 변하게 될 경우 연결리스트를,

이미 만들어진 구조에서 데이터의 접근하는 작업이 필요할때는 배열이 좋겠다.

하지만 Case by Case 이므로 목적에 따라 선택해야한다.