[자료구조]배열과 연결리스트

Array vs Linked List

• 배열은 고정된 양의 데이터를 임시로 저장해두고 수시로 데이터에 접근하는 경우에 유용하게 사용될 수 있으며, 연결리스트는 데이터의 추가와 삭제가 빈번하게 일어나거나, 복잡한 형태의 자료구조를 만들 때 유리하다.

배열

---

• 논리적 저장 순서와 물리적 저장 순서가 일치해 인덱스(index)로 해당 원소(element)에 접근할 수 있다.
• 인덱스 값을 알고 있으면 Big-O(1)로 접근할 수 있다.
• 하지만 원소를 삭제, 삽입시, 배열의 연속적인 특징은 깨진다.
• 따라서 삭제 및 삽입시 해당 인덱스보다 큰 인덱스를 갖는 원소들을 이동해야하고 이 경우의 시간 복잡도는 O(n)가 된다.
• 데이터의 삽입 또는 삭제 등의 연산이 빈번하게 발생하여 데이터의 수가 다이나믹하게 변하게 되는 자료구조에서는 배열을 활용하는 것이 비효율적

연결리스트

---

• 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 삭제와 삽입을 O(1) 만에 해결
• 하지만 단점은 원하는 위치를 찾는 과정에 있어서 첫번째 원소부터 다 확인해야한다.
• 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생
• 자료에 대한 접근이 잦은 자료구조에서는 연결리스트의 사용을 지양해야 한다.
• 그런데, 배열과 달리 노드를 추가하고 제거하는 과정을 통해 최대 노드의 수를 언제든지 변경할 수 있기 때문에, 메모리 공간을 유동적으로 사용할 수 있다.
• Tree 구조의 근간이 되는 자료구조

리스트

• 리스트는 배열과 유사하지만 빈 공간이 없이 순차적으로 자료가 저장된다는 특징이 있음
• 즉 중복을 허용하면서 순서가 있는 자료구조
• C언어에서는 리스트를 지원하지 않고 배열만 지원(처음 정적으로 저장공간을 할당하고 인덱스를 활용해 데이터를 삭제하면 해당 공간은 빈 공간으로 남아있음), 자바스크립트는 배열에 리스트의 기능을 포함
• 파이썬에서는 배열을 지원하지 않고 리스트만 지원함, 자바에서는 ArrayList와 LinkedList를 나누어 지원