Array vs Linked List

Array

---

• 논리적 저장 순서와 물리적 저장 순서가 일치.(index를 활용하여 해당 element에 접근 할 수 있다.)
• 해당 원소에 인덱스를 알고 있으면 O(1)이라는 시간 복잡도를 갖는다.
• Random Access가 가능하다.
• 하지만 삭제 또는 삽입과정에서 비용이 많이 발생한다.
  • 해당 원소의 삽입 과정에서 맨 뒤의 경우를 제외하고 원소들이 있는 처음 또는 중간에 넣게 된다면 삽입할 공간을 만들기 위해 해당 원소들이 뒤로 이동해야하는 비용이 발생한다.
  • 해당 원소의 삭제 과정에서 해당 원소를 삭제 한 후 빈 공간이 생긴다. 이 빈 공간을 매우기 위해 빈 공간 다음으로 이어지는 원소들을 한 칸씩 앞으로 떙겨야 하므로 비용이 발생한다.
  • 비용에 대한 시간 복잡도는 O(n) 이다.

 

Linked List

---

• 배열에 대한 삽입,삭제 과정에 따른 많은 비용이 발생하는 문제점을 해결하기 위한 자료구조이다.
• 각 원소들은 다음에 있는 원소의 위치를 알고있다.(즉 기억하고 있다,저장하고 있다)
• 이 위치에 대해 변경만 해준다면 삽입 삭제 비용이 O(n)이 아닌 O(1)이 된다.
• 삽입,삭제가 편리해 보이지만, 다음 위치를 이어줄 원소를 찾는데 시간이 걸린다.
  • 첫번째 원소부터 다 확인해야 한다.
  • Array와 달리 논리적, 물리적 저장순서가 일치하지 않는다.
  • 삽입하고 삭제하는 과정만을 보면 효율적으로 보이지만 삽입하고자 하는 위치, 삭제하고자 하는 위치를 찾는데 있어서 비용이 O(n)이 소요된다.
  • Array보다 나은 점이 하나도 없을 수 있다. 하지만 트리구조에 매우 유용하게 사용되는 자료구조이며 '트리' 에서 사용할 때 매우 효율적인 탐색이 가능하도록 할 수 있다.

'

요약

---

• 데이터의 접근 속도

배열이 더 빠르다.

해당 인덱스 만 알고 있다면 O(1)이라는 시간 복잡도를 갖는다.

링크드 리스트는 탐색에 대한 시간 소요로 인하여 O(n)을 갖는다.

 

• 데이터의 삽입 / 삭제 속도

연결리스트가 더 빠르다.

만약 배열이 공간이 여유롭고 맨 끝에 삽입한다면 O(1)에 가능하지만, 처음 그리고 중간에 삽입/삭제 할 경우 해당 인덱스 부터 끝까지 배열의 원소들의 뒤/앞으로 밀려야하는/떙겨오는  비용이 발생한다.

 

삽입/삭제가 빈번하다면 링크드 리스트 사용을 권장한다고 한다.

이미 만들어진 구조에서 데이터의 Access 측면에서는 배열이 좋다.