✔ 1. 리스트(배열)란?

리스트는 동일한 형태의 자료들을 논리적 순서대로 메모리에 연속 저장하는 구현방식이다. 따라서 논리적인 순서와 물리적인 순서가 일치해야한다.
즉, 원소들을 나열하는 것이다.
[일차원배열]

[이차원배열]

다차원배열은 1차원 논리 순서를 행 또는 열 우선순위에 따라 변환시킬 수 있다.

✔ 2. 배열의 기능

• 생성 : 총 배열의 길이, 배열의 사이즈, 예외처리
• 값 가져오기 : 사용자가 요청한 k 번째 값을 가져올 때는 배열의 크기를 체크해야한다.
• 원소삽입 : 삽입할 자리 이후에 있는 원소들을 한 자리씩 뒤로 이동시킨다. 뒤로 이동해 삽입할 자리가 비워지면 원소를 삽입한다. 따라서 n개의 원소로 이루어진 배열에 k 번째에 자리를 삽입하는 경우 n-k개의 원소를 이동시켜야 한다. 삽입할 때는 overflow가 발생하는지 체크해야한다.
• overflow : 빈자리가 없어 새 항목을 삽입할 수 없을 때, 배열 크기를 2배로 확장한다.
• underflow : 배열의 3/4이 비어있다면 배열 크기를 1/2로 축소한다.
• 원소삭제 : 원하는 원소를 삭제한 후, 삭제한 자리 이후의 원소들을 앞에서부터 한자리씩 이동시킨다. 따라서 n개의 원소로 이루어진 배열에 k번째 원소를 삭제하는 경우 n-k-1개의 원소를 이동시켜야한다. 삭제할 때에는 underflow가 발생하는지 체크해야한다.

✔ 3. 배열의 응용

행렬

행렬(matrix)란 행과 열로 구성된 자료구조로 2차원 배열로 구현이 가능하다.

다항식

(차수+1) 개의 배열을 만들어 지수의 내림차순에 따라 계수를 넣는다. 하지만 차수가 1000이지만 항이 3개인 다항식(3x^1000+2x+6) 인 경우 998개의 배열 원소에 대한 메모리가 낭비되므로 지수,계수 별로 2차원 배열을 이용할 수 도 있다.

✔ 5. 배열 수행시간

• 값가져오기 : O(1)
• 가장 맨 뒤 삽입/ 삭제 : O(1)
• 중간에 삽입/ 삭제 : O(N)
• overflow/underflow : O(N)

✔ 6. 링크드리스트란?