[자료구조]리스트(List)와 배열(Array)

리스트

데이터를 일직선으로 줄줄이 정렬한 데이터 구조.
데이터의 추가나 삭제는 쉬운 반면, 원하는 데이터에 접근(검색)하는 시간은 오래걸린다.
Data1 - (포인터) → Data2 - (포인터) → Data3

• 위와 같이 포인터가 다음 데이터의 주소를 가리키는 형식으로 되어있기 때문에 메모리상에 각 데이터가 연속적으로 배치 될 필요가 없다. 그렇기 때문에 예를들어 Data3에 접근하기 위해서는 반드시 Data1 → Data2 를 거치는 형식으로 순차접근이 필요하다.
• 새로운 데이터를 추가하는 경우, Data1 → Data2 → Data3 중 예를들어 Data1과 Data2 사이에 new Data를 추가하고 싶다면 Data1 - (포인터) → Data2 의 포인터가 new Data를 가리키도록 포인터의 주소만 변경해주고, new Data의 다음 포인터의 주소를 Data2를 가리키도록 변형해주면 된다.

✅ 저장되어 있는 데이터의 개수가 n개라면 데이터는 접근할 때 순차접근(선형 탐색)을 사용하므로, 계산시간은 O(n)이 소요된다. 반면 저장과 삭제의 경우 해당하는 데이터의 포인터만 변경하면 되므로, 전체 데이터개수 n개의 영향을 받지 않아 상수 시간 O(1)이 소요된다.

배열

데이터를 한 열로 연속해서 정렬하는 데이터 구조.
리스트와 반대로 데이터의 접근(검색)은 편리하지만, 추가,삭제의 경우 시간이 오래걸린다.
데이터는 메모리의 연속된 영역에 순차적으로 저장 되며, 각 데이터는 Index를 갖는다.

• 연속적으로 저장되어있기 때문에 메모리상의 위치는 인덱스를 바탕으로 계산할 수 있고, 각 데이터에 직접 접근 할 수 있다.

✅ 저장되어 있는 데이터의 개수가 n개라면, 데이터에 접근할 때는 전체 데이터 개수와 상관없이 해당 데이터의 인덱스로만 직접 접근이 가능하기 때문에 계산에 상수 시간 O(1)이 소요된다. 반면 데이터를 추가,삭제 하는 경우 모든 데이터를 하나씩 뒤로 옮기며 공간을 추가로 확보는 연산이 발생하기 때문에 O(n)의 시간이 소요된다.

배열 탐색

1. 선형 탐색

• 데이터가 순서없이 뒤죽박죽으로 나열된 경우에도 적용할 수 있다.
• 단순히 배열의 앞쪽부터 순서대로 데이터를 조사하는 방식을 사용한다.
• 선형 탐색은 데이터의 처음부터 순서대로 비교를 반복한다. 따라서 데이터가 많고 찾는 데이터가 배열의 끝에 있거나 없는 경우 비교 횟수가 많아져서 시간이 오래걸린다. → O(n)

2. 이진 탐색

• 데이터가 정렬 된 경우에만 사용할 수 있다.
• 찾으려는 데이터와 배열의 정중앙 데이터를 비교하여 중앙을 기준으로 값이 왼쪽에 있는지 오른쪽에 있는지 판별하여 검색의 범위를 절반으로 줄여나가는 방식
• 데이터를 찾거나 데이터가 없다는 것이 확실해 질 때 까지 이 방법을 반복한다.
• n개 있던 데이터를 절반씩 줄이는 조작을 log2N번 반복하면 데이터는 1개가 된다.
  따라서 연산시간은 →O(logN)