[자료구조 · 알고리즘] 선형 배열 (Linear Arrays)

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다.

 

 

선형 배열 (Linear Array)은 데이터들이 선(=line)처럼 일렬로 늘어선 형태이다.

 

자바, C에서 볼 수 있듯이 같은 종류의 데이터가 담긴 '배열'과 다르게, 파이썬에서의 리스트는 각 원소가 서로 다른 데이터 타입을 가지고 있어도 된다. 문자열의 경우, 문자열 길이가 다른 것 역시 상관없다.

 

 

리스트 길이와 관계없이 빠른 결과 시간

L = ['Bob', 'Cat', 'Spam', 'Programmers']

L.append('New')

L.pop()

 

먼저 리스트 L을 선언하였다.

 

append는 리스트의 가장 마지막 인덱스에 원소를 추가한다.

pop은 마지막 인덱스에서 요소를 꺼낸다.

 

append와 pop 모두 가장 마지막 인덱스에 값을 넣거나 빼기 때문에, 실행시간은 리스트 길이와 무관하다.

 

 

리스트 길이에 비례하는 결과 시간 (선형 시간)

L = [20, 37, 58, 72, 91]

L.insert(3, 65)

del(L[2])

 

정수 요소를 가진 리스트 L이다.

 

insert를 통해 3번째 인덱스에 65라는 값의 원소를 삽입한다.

del을 통해 2번째 인덱스, 즉 3번째 요소의 값을 삭제한다.

 

위의 경우, 리스트 길이가 길수록 처리시간이 증가한다.

insert로 원소를 삽입할 경우 3번째 인덱스의 요소 추가를 위해 4, 5번째 인덱스가 먼저 뒤로 이동한 후 진행된다.

del은 기존의 2번째 인덱스의 값이 제거된 후, 뒤의 요소들이 한 칸씩 앞으로 당겨온다. 그다음 마지막 인덱스가 삭제되면서 총 5개의 요소가 담긴 리스트가 되는 것이다.

 

리스트 길이에 비례한다는 점에서 이는 선형 시간이며 O(n)으로 표현할 수 있다.