[알고리즘] 선형 배열

선형배열(Linear Array)

• 배열(리스트) : 같은 자료형을 가진 데이터가 연속적으로 저장된 자료구조

Array는 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에, 인덱스를 사용한 직접 접근이 가능하다 => 배열의 각 요소가 메모리상에서 연속적으로 저장된다는 의미

리스트 관련 메서드

• array[index]를 통한 접근은 (O(1))이다.
• list.append(iterable) : 맨 뒤에 원소로 그대로 덧붙이기
  - 평균적으로는 (O(1))
  • 하지만 동적 배열 형태를 사용하는 Python에서는 초기에 할당된 크기에서 더 큰 메모리 공간이 필요한 경우, 더 큰 크기로 확장된다.
  • 이 경우, 기존 요소를 더 큰 공간의 메모리 공간으로 복사하는 작업이 필요하다.
  • 이 경우에는 (O(n))이 될 수 있다.
• list.extend(iterable) : 맨 뒤에 원소로 추가하기
  - 추가되는 요소의 개수가 m개일 경우, (O(m))이 된다
  
• list.pop() : 맨 뒤의 원소 하나 꺼내기
  - 별도의 인덱스를 지정하지 않았다면, 가장 마지막 요소를 제거하기 때문에 (O(1))이다.
  • 하지만, 별도의 인덱스를 지정하여 pop을 했다면 pop 과정 후 추가적인 shift 작업이 필요하므로 이 경우, (O(n))이 될 수 있다.

append와 extend 메서드 차이
=> append 함수는 값을 그대로 붙이지만, extend 함수는 원소로 추가한다.

<append 함수 사용>

list1 = ['A', 'B', 'C']
list2 = ['D', 'E']

# append
list1.append(list2)

# ['A', 'B', 'C', ['D', 'E']]
print(list1)

<extend 함수 사용>

list1 = ['A', 'B', 'C']
list2 = ['D', 'E']

# extend
list1.append(list2)

# ['A', 'B', 'C', 'D', 'E']
print(list1)

리스트 길이와 실행 시간이 비례하는 메서드 (O(n))

• list.insert(index, iterable) : 특정 위치에 원소 추가
• del(index)/ del list[index] : 특정 위치 원소 삭제하기
• list.index(data) : 특정 값(data)가 존재하는 위치를 돌려준다.