Array(배열)

• 데이터가 많아지면 그룹 관리의 필요성이 생겨 프로그래밍에서 사용하게 된 것이 배열이라는 자료구조
• 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합하면 많은 정보도 효율적으로 처리할 수 있다.
• 배열 인덱스는 값에 대한 유일무이한 식별자

배열의 특징

• 크기가 정해져있고 기능이 없다.
  (배열의 장점이자 단점, 다른 자료구조의 좋은 부품으로 사용될 수 있다.)
• 데이터의 공간으로 한번 정해지면 바꿀 수 없다.
  
  1. 인덱스를 가지며, 원소의 인덱스는 변경되지 않는다.
  2. 처음 크기를 10으로 지정한다면 5개의 데이터만 저장해도 실제 배열의 크기는 10이다.
• 인덱스를 활용해 빠르게 조회가 가능하다. $O(1)$ 내에 접근할 수 있다.

배열의 한계

• 원소를 중간에 삽입/삭제하려면 모든 원소를 다 옮겨야한다. 최악의 경우 배열의 길이 N 만큼을 옮겨야 하므로 $O(N)$의 시간 복잡도를 가진다.
  • 기존 배열은 그대로 두고,
  • 새로운 길이로 지정된 배열을 따로 할당 후(메모리가 있는지 탐색 필요)
  • 데이터의 복사를 진행하고,
  • 기존의 배열을 삭제한다.
  • 총 3번의 작업 + 메모리 탐색이 필요하기 때문에 리소스 낭비가 크다.
• 위와 같은 한계를 해결하기 위해 linked list 자료형을 활용할 수 있다.(탐색, 할당, 복사, 삭제 등의 리소스 낭비가 없다.)
• 인덱스에 따라 값을 유지하므로 원소가 삭제되어도 빈자리(Null)가 남게 되어 메모리가 낭비된다.
  • 조건문을 통해서 빈 엘리먼트를 제외할 수 있으나, 조건문을 많이 사용하는 것은 좋지 않다.
• 삭제한 데이터를 뒤에 위치한 원소로 메꾸면, 데이터가 순서에 따라 빈틈없이 연속적으로 위치하며 이를 list(리스트)라고 한다.
• 인덱스가 중요한 경우 배열을 사용, 인덱스가 중요하지 않은 경우 리스트를 사용한다.
  
  

list(리스트)

• 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 데이터 스트럭쳐(자료구조)
• 리스트 자료구조의 핵심은 요소들간의 순서, 따라서 리스트를 다른 말로 시퀀스(sequence, 순서)라고도 부른다. 즉 순서가 있는 데이터의 모임이 리스트이다.
• 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가진다.
• 빈 엘리먼트는 허용하지않는다.(엘리먼트=요소=원소=element)
• 순차성을 보장하지 않아서(Spatial locality) 캐시 적중(cache hit)이 어렵다.
• 데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.

list 자료구조의 대표 기능(operation)

자료구조에서 가장 중요한 점은, 해당 자료구조가 어떠한 기능을 가지고 있느냐는 것이다.

• 처음, 끝, 중간에 요소를 추가/삭제하는 기능
• 리스트에 데이터가 있는지를 체크하는 기능
• 리스트의 모든 데이터에 접근할 수 있는 기능

LinkedList(링크드 리스트)

• 노드(화물칸)와 포인터(연결고리)로 구성
• 특정 원소를 조회하기 위해 포인터를 따라 탐색해야 한다. 최악의 경우 모든 노드를 탐색해야 하므로 $O(N)$의 시간 복잡도를 가진다.
• 원소를 중간에 삽입/삭제하려면 앞 뒤의 포인터만 변경하면 된다. 따라서 원소 삽입/삭제를 $O(1)$의 시간 복잡도 안에 할 수 있다.

Arary vs LinkedList

경우	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array를 사용하자	삽입과 삭제가 빈번하다면 LinkedList를 사용하는 것이 더 좋다.