[자료구조와 알고리즘]2. 선형 배열

데이터가 일렬로 늘어져 있어서 붙여진 이름

배열

• 같은 종류의 데이터가 줄지어 늘어서 있는 것
• 원소들을 순서대로 늘어놓은 것
• 인덱스는 0부터 시작한다

리스트

• 파이썬에서는 배열이라는 데이터보다는 리스트를 쓴다
• 배열보다 더 융통성이 있는 데이터 타입이다

리스트 연산
1. 상수 시간
1) 원소 덧붙이기 : l.append()
2) 끝에서 꺼내기 : l.pop() / 마지막 원소를 반환한다

이 두 가지 연산은 순식간에 빠르게 할 수 있는 일
리스트의 길이와 무관하다(상수시간) : O(1)

2. 선형 시간: 리스트의 길이에 비례 O(n)
   리스트의 길이에 따라 다른 애들도 있다
   삽입, 삭제 등의 경우에 이 정도 걸린다

1) 원소 삽입 : l.insert(3, 65)
//3번째 자리에 65를 넣기
//맨 끝에 원소를 덧붙이는 것보다는 오래 걸린다: 한칸씩 뒤로 넘기니가

2) 원소 삭제 : del(L[2])
//맨 끝에 원소를 덧붙이는 것보다는 오래 걸린다
//리스트 L의 2인덱스의 원소를 삭제 : 한칸씩 앞으로 당가니까

3. 리스트(배열) 연산
   1) 원소 탐색하기
   l.index(원소)

정렬된 리스트에 주어진 원소 삽입하기
1)삽입할 위치 찾기
2) 해당 위치에 원소 삽입
그 결과를 여전히 정렬된 상태 유지하는 리스트
주어진 리스트에서 트겆 원소를 모두 차자아내라

리스트 L은 정수 원소

올바른 위치에 x를 삽입
결과 리스트를 반환
인자로 주어지는 리스트 L : 정수 원소들로 이루어져 있으며 크기에 따라 오름차순 정렬