연결 리스트와 배열 (Linked list)

▶연결 리스트

---

종류는 단일/이중/원형 연결 리스트가 있다. 

데이터를 가진 노드를 포인터로 연결해 놓은 자료구조이다.

연결리스트는 데이터의 추가/삭제가 O(1)의 시간에 가능하다는 장점이 있지만 (다음 노드의 주소만 변경해주면 됨)

배열과는 달리 특정 위치의 데이터 찾기가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.

(가장 앞이나 뒤에 있는 노드부터 포인터를 하나씩 이동해가며 데이터를 찾아야함)

▶배열

---

번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료구조로, 같은 종류의 데이터들을 순차적으로 저장한 것을 말한다.

특정 위치의 데이터에 접근하는 것이 O(1)의 시간에 가능하다는 장점이 있지만 (인덱스로 데이터에 바로 접근)

데이터 추가/삭제가 최악의 경우 O(N)의 시간이 걸린다는 단점이 있다.

(데이터를 삭제했을 경우 그 뒤에 순차적으로 저장된 데이터들을 모두 앞으로 당겨 저장해줘야하고

추가했을 경우 모두 뒤로 밀어 저장해줘야함.)

▶Tip

---

데이터의 추가/삭제가 빈번한 경우 연결리스트를 사용하는 것이 효율적이고

저장된 데이터에 접근하는 것이 빈번한 경우 배열을 사용하는 것이 효율적이다.

연결 리스트는 사이즈가 동적이지만, 배열은 사이즈가 고정적이다.

정확한 최대 크기를 알 수 없는 경우 공간을 동적할당하는 방향으로 구현하는 것이 좋다.