Array vs LinkedList

둘다 선형 방식의 자료구조이다.

배열(Array): 인덱스를 가지고 있는 데이터의 모음.

리스트(List): 순서가 있는 데이터의 모음. 각 원소는 다음이 어떤 원소인지만 알고 있음.

---

배열은 인덱스를 가지고 있기 때문에

• 인덱스를 알고 있으면 원소에 직접 접근이 가능해 빠르게 조회할 수 있다.(O(1))
• 대신 인덱스는 고정되어야 하고 만약 엘리먼트가 삭제되더라도 빈 공간으로 남겨둬야 한다.
  
  → 이는 메모리 낭비를 초래할 수 있고, 엘리먼트가 비었는지 확인하는 로직이 필요하다.

리스트는 인덱스가 없기 때문에

• 각각의 원소는 다음 원소만 알고 있기 때문에 순차적으로 접근해야 한다. (O(n))

• 인덱스가 고정이 아니고 순서 정도의 의미만 지니기 때문에 추가, 삭제가 빠르다.(O(1))
  
  → 하지만 추가 삭제를 위한 원소를 찾기 위해 O(n)의 시간이 필요하므로 결국 추가, 삭제도 O(n)의 시간 복잡도를 갖고 있다.

• 인덱스는 없어 낭비없이 데이터를 적재할 수 있지만 다음 데이터를 가리키는 포인터가 필요하기 때문에 배열에 비해 추가적인 공간이 필요하다.