[자료구조] 선형 배열(Linear Array)

오늘은 자료구조 중 배열에 대해 알아보려고 한다!

배열과 리스트

배열(Array): 동일한 자료형의 데이터를 여러개 저장하기 위해 한 번에 많은 기억 공간을 만들어 두고 사용하는 기본 자료구조. 행렬 문제나 탐색, 정렬 등에서 사용

• 차례대로 접근하는 순차처리 접근 방식
• 새 데이터 삽입이나 삭제 시 많은 시간 소요

파이썬에는 배열이 없고 대신 리스트(list) 형식을 사용한다.
리스트는 배열보다 유연한 형태의 자료구조이다. 두 구조의 차이점은 다음과 같다.

• 배열: 같은 data type으로만 구성 가능
• 리스트: data type에 상관없이 구성 가능

리스트 연산

• 원소 덧붙이기: L.append('New')
• 끝에서 꺼내기: L.pop()
  • L.pop()의 출력 값은 마지막 원소이고, 해당 연산을 수행한 뒤에 리스트에서 해당 원소는 제거된다.
  • L.pop() 괄호안에 숫자를 넣어주면 해당 index의 원소가 출력되고, 리스트에서 해당 원소는 삭제된다.

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

• 원소 삽입하기: L.insert(index, value)
  • index 위치에 value값을 입력
• 원소 삭제하기: del(L[index])
  • index 위치의 원소 삭제

-> 위 두가지는 연산은 리스트의 길이가 길면 오래 걸리는 연산이다.즉, 리스트의 길이에 비례(선형시간)

• 원소 탐색: L.index(value)
  • value값을 가지는 원소의 index값 출력
  • value값을 가지는 원소가 여러개일 경우 맨 처음에 등장하는 원소의 index 출력
  • value값이 리스트에 존재하지 않을 경우 ValueError 발생

del vs pop

• del은 삭제되는 원소의 값을 출력하지 않는다.
• pop의 경우 삭제되는 원소의 값을 출력해주므로 삭제하는 값을 저장할 수 있다.
• 또한 del의 경우 index위치에 슬라이싱을 활용하여 여러 개 삭제가 가능하다.