[자료구조] Array 와 LinkedList의 차이

Array(배열) : 연결된 메모리를 보장하여 중간데이터에 빠르게 탐색이 가능하지만 삽입이나 삭제의 경우에데이터를 전부 이동해야하기에  비효율적이다.

Array(배열)는 가장 기본적인 자료구조로 정적 자료구조이다.

인덱스를 통해 해당 원소에 접근가능하다. 따라서 시간 복잡도는 0(1)으로 빠르게 찾을 수 있다.  Random access가 가능하다는 장점이 있어 접근과 탐색에 용이하다. 

 

하지만 삭제나 삽입 과정에서 원소에 접근해서 작업을 할 때는추가적인 작업이 발생해 시간이 더 걸린다. 예를 들면 어느 원소를 삭제한다고 했을 때 연속적인 배열이 깨지기 때문에 빈공간이 생긴다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 움직이기에 비용(cost)이 발생하고 시간복잡도는 0(n)이 된다.  삽입도 마찬가지이다. 

array[3] = D로 접근 가능, 하지만 D를 삭제하려면 메모리 한칸씩 당겨야 됌

 

---

LinkedList(연결리스트) : 동적메모리로 삽입이나 삭제가 자유롭지만 구현이 복잡하고 중간 데이터에 접근하기 위해서는 이전 노드들을 모두 거쳐야만 접근 가능하기에 비효율적이다.

LinkedList(연결리스트)는 동적 자료구조이다. 따라서 크기의 제한이 없다. 대신 노드라는게 존재하며 그 노드안에 데이터가 있고, 다음 데이터를 가리키는 주소를 가지고 있는 연결되어 이어진 형태이다. 그래서 데이터 추가, 삭제가 자유롭다는 장점이 있다. 하지만 배열과 다르게 연속적인 메모리 주소를 할당 받지 않기 때문에 Random acess는 불가능하다. 즉, 데이터를 탐색할 때 순차적으로 접근한다는 것이다. 결국 연결리스트는 탐색에도 0(n)의 시간복잡도를 갖고 삽입 삭제에도 0(n)의 시간복잡도를 갖는다. 이 연결리스트가 Tree 구조의 근간이 되기에 꼭 알아야되며 유용성이 있다.

D를 삭제하려면 C에서의 링크를 E로 변경 but, D에 접근하기 위해 B, C 모두 거쳐야함

 

Array(배열)	LinkedList(연결리스트)
정적 자료구조	동적 자료구조
크기 제한 있음	크기 제한 없음
연속된 메모리 주소 할당	연속된 메모리 주소 할당 받지 않음
Stack(스택) 영역에 메모리 할당	Heap(힙)영역에 메모리 할당
접근, 탐색 용이	추가, 삭제 용이
Index 존재	Node 존재
정보 저장시 활용(장바구니 역할)	음악플레이어 앱에 앞 뒤 곡 연결 포토샵 histroy 기능
-	단일연결리스트, 이중연결리스트,다중연결리스트, 원형연결리스

연결리스트의 종류 

 

1. 단순 연결 리스트 : 단방향

이전 노드에 접근하기 위해서는 첫번째노드부터 다시 순회 

2. 이중 연결 리스트 : 양방향

이전 노드에 직접 접근 가능하며 각 노드가 앞뒤로 연결

3. 원형 연결리스트 : 단방향

이전 노드에 접근하기 위해서 계속 한 방향으로만 순회하며 마지막 노드와 첫번째 노드가 연결된 원형 구조