Array VS Linked List

참고

• ahribori.com/article/591a5824c686bd0d48e95f47
• woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/

배열(Array)

특징

• 데이터를 물리적 주소에 순차적으로 저장한다.
• 인덱스를 가지고 있기 때문에 인덱스를 알고 있다면 바로 접근이 가능하다. 시간복잡도 O(1)
• 크기가 정해져 있기 때문에 삽입 시 공간이 부족하면 배열을 늘리는 연산을 해야한다.
• 삽입과 삭제 시 모든 데이터를 한 칸씩 앞 뒤로 미뤄야하는 비용이 든다.
• Array가 할당되어 지면 즉시 compile time에 할당된다. 이를 정적 메모리 할당이라 한다.
• Stack 영역에 메모리가 할당된다.

 

연결 리스트(Linked List)

특징

• 데이터 뿐만 아니라 다음 데이터의 물리적 주소까지 같이 저장한다.
• 단순 연결은 다음 데이터 주소로만 노드를 구성하고, 이중 연결은 전 후 노드로 구성된다.(위 사진은 이중 연결이다)
• 링크를 따라 검색되기 때문에 배열에 비해 접근 속도가 느리다.
• 삽입 삭제 시 해당 위치까지 탐색 후 노드를 노드들 중간에 삽입하거나 노드를 제거하기만 하면 된다.
• 노드 할당 시 runtime에 할당되며 이를 동적 메모리 할당이라 한다.
• Heap 영역에 메모리가 할당된다.

Array Vs LinkedList

# 데이터 접근 속도

Array는 인덱스를 사용하여 바로 접근이 가능하다. 시간 복잡도는 O(1)이다.

LinkedList는 노드가 링크로 연결되어 순차 접근 방식을 사용한다. 그렇기 때문에 첫 노드부터 원하는 노드를 찾을 때까지 진행된다. 시간 복잡도는 O(n)이다.

# 데이터 삽입 삭제 속도

Array는 삽입 시 크기가 부족하다면 늘리는 연산이 필요하며, 삽입과 삭제 시 모든 데이터를 한칸씩 옮겨야 한다. 그렇기 때문에 많은 시간이 걸린다.

LinkedList는 삽입 삭제 할 노드까지 순차적으로 검색 후 해당 위치나 노드를 삽입 삭제하기 때문에 O(n)의 시간이 걸리지만 모든 데이터를 옮길 필요가 없다. 첫 부분과 끝 부분에 데이터 삽입 시 시간 복잡도는 O(1)이다

# 결론

Array는 데이터 접근이 자주 일어나는 경우에 사용한다.

LinkedList는 삽입 삭제가 자주 일어나는 경우에 사용한다.