List

자료를 구조화하는 방법으로 나열하는 것.
자료들 간에 순서를 갖는 리스트를 선형 리스트라 한다. 배열과 유사

선형 리스트의 대표적인 예
선형 순차 리스트 : 원소를 논리적인 순서대로 메모리에 연속하여 저장하는 순차 자료구조
선형 연결 리스트 : 원소를 논리적인 순서대로 연결하여 구성하는 연결 자료구조

선형리스트는 탐색, 삽입, 삭제의 기능이 있다.

1. 삽입 알고리즘 : 삽입할 빈 자리를 만들고, 이후의 원소들을 한 자리씩 뒤로 자리 이동.
2. 삭제 알고리즘 : 원소 삭제 -> 이후의 원소들을 한 자리씩 앞으로 자리 이동.
3. 배열을 사용했을 때는, 인덱스 번호로 탐색하기 때문에 탐색 알고리즘은 없음!

리스트 종류

• 배열
• 단순연결리스트
• 이중연결리스트
• 원형연결리스트

배열

동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조
탐색 시 인덱스 사용 -> O(1) 시간에 접근 가능
삽입, 삭제 시 이후의 항목들을 한 칸씩 앞이나 뒤로 이동해야 하므로, 항상 O(1)시간에 수행할 수 없다.
(char배열 한 칸 = 2byte, int배열 한 칸 = 4byte)

배열은 정해진 크기의 메모리 공간을 할당받아 사용하므로, 빈 자리가 없어 새 항목을 삽입할 수 없을 때 overflow 발생
배열이 비었을 때 탐색, 삭제를 수행할 시 underflow 발생

overflow발생관련 해결방법

• overflow가 발생하면 배열 크기 2배 확장
• 배열의 3/4가 비었다면 배열 크기를 1/2로 축소

선형리스트의 단점, 어쩌구
보완하기 위해 연결리스트 등장!