선형 배열(Linear Arrays)

1 선형 배열이란?

• 선형 배열: 데이터들이 선처럼 일렬도 길게 늘어서 있는 배열
• 파이썬에서 리스트를 활용해 구현 가능

• 배열: 원소들을 순서대로 늘어놓은 것
  • python에는 없는 자료형(C++, java 등 다른 언어에 존재)
  • 같은 타입의 데이터만 포함할 수 있다
• 리스트: python에서의 원소들을 순서대로 늘어놓은 것
  • 서로 다른 데이터 타입을 가질 수 있다

2 파이썬에서의 리스트 (배열) 연산

• 상수 시간 연산(O(1))

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

  • 원소 덧붙이기 (append())

    L.append("New") # 끝에 하나의 원소를 넣는다

  • 끝에서 꺼내기 (pop())

    • parameter로 idx 값을 넣으면 그 idx에 있는 값이 삭제되고 반환된다

      L.pop() # 끝에서 하나의 원소를 꺼낸다 (리스트에도 그 원소가 없어짐)
      

• 선형 시간 연산

  리스트의 길이에 비례해 실행 시간이 달라지는 연산
  → O(n)

  

  • 원소 삽입하기

    arr.insert(idx, value) # idx 위치에 value를 삽입한다

    • 이미 값이 있는 자리에 원소를 입력하므로 idx에 있던 원소부터 뒤로 밀려나게 된다

  • 원소 삭제하기

    del(arr[idx]) # arr의 idx 위치에 있는 값을 삭제한다

    • 삭제한 값의 자리를 채우기 위해 idx+1에 있던 원소부터 앞으로 당겨온다
    • pop()과의 차이점: pop()은 삭제된 값을 반환하지만, del은 그렇지 않다

  • 원소 탐색하기

    • 리스트 내에 원소가 있는지, 있다면 어디에 있는지 탐색한다

    • 탐색 알고리즘은 리스트의 길이와 여러 조건에 따라 시간이 달라질 것이다 (선형 시간일 것이다)

      arr.index("A") 
      # arr 내에 없는 값을 입력하면 오류가 난다