배열과 연결 리스트 정리 (Array / Linked list)

🦥 배열 (Array)

🌴 특징

• 같은 타입의 데이터를 나열한 선형 자료구조(sequence container)다.
• 배열의 크기는 선언 시점에 정해져야 한다.
• 생성 시 stack에 메모리가 할당된다.

🌴 시간 복잡도

• 삽입/삭제
  • 배열의 맨 앞에 삽입/삭제하는 경우 : O(n)
  • 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
  • 배열의 중간에 삽입/삭제하는 경우 : O(n)
• 탐색 (인덱스 접근) : O(1)

🌴 장점

• 인덱스 접근 가능 : 인덱스를 통해 임의의 원소에 접근(random access)이 가능하다. 자료구조의 크기가 클수록 더 강력한 장점이 된다.
• 연속된 메모리에 할당 : 주소값으로 원소에 접근할 수 있어서 관리가 편하다.

🌴 단점

• 삽입과 삭제가 어렵고 오래 걸림 : 원소를 삽입하거나 삭제할 경우, 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야 한다. (연속된 메모리에 저장되기 때문)
• 배열의 크기는 고정적 : 배열의 크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 선언한 뒤 기존 원소들을 복사해야 한다.
• 공간 낭비 발생 가능 : 연속된 메모리를 사용하기 때문에 중간에 데이터가 삭제되면 공간 낭비가 발생할 수 있다. ex. 처음에 배열 크기를 100으로 생성했는데 10정도 밖에 쓰지 않으면 나머지 공간은 빈 공간으로 낭비가 발생한다.
• 메모리를 많이 사용 : 연속적인 메모리 할당이 필요하기 때문이다.

🌴 언제 사용할까

• 데이터 개수가 확실하게 정해져 있을 때
• 데이터의 삭제와 삽입이 적을 때
• 검색을 해야할 때

---

🦥 리스트 (Linked list)

🌴 특징

• 데이터를 순차적으로 저장하는 선형 자료구조 (sequence container)
• 노드를 연결하여 만든 리스트
  • 첫번째 노드를 헤드(head), 마지막 노드를 테일(tail)이라고 한다.
  • 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다.
• 생성 시 heap에 메모리가 할당된다.

🌴 시간 복잡도

• 삽입
  • 리스트의 맨 앞/뒤에 삽입하는 경우 : O(1)
  • 리스트의 중간에 삽입하는 경우 : O(n) (탐색하는 시간)
• 삭제
  • 리스트의 맨 앞/뒤에서 삭제하는 경우 : O(1)
  • 리스트의 중간에서 삭제하는 경우 : O(n) (탐색하는 시간)
• 탐색 : O(n)

🌴 장점

• 삽입과 삭제가 용이 : 포인터로 연결되어 있어서 가리키는 노드만 변경해주면 됨
• 크기가 가변적 : 새로운 원소 추가 시 동적으로 크기가 변경된다.
• 불연속적 메모리 할당 : 빈 공간 없이 데이터를 저장할 수 있다. (ex. 중간 데이터 삭제 시)
• 사용한 메모리를 재사용할 수 있다

🌴 단점

• 인덱스 접근(ex. [], .at(i))이 불가능 : 반복자를 이용하여 탐색(sequential access)하기 때문에 속도가 느리다.
• 포인터로 인한 저장 공간의 낭비 : 다음 노드 가리키는 포인터를 저장하는 공간이 필요하다.

🌴 언제 사용할까

• 크기가 정해져 있지 않을 때
• 삽입과 삭제가 자주 일어날 때
• 검색을 자주 하지 않을 때