자료구조/알고리즘_배열

본 포스팅은 python 언어 기준으로 작성됩니다.

append

lst = [1, 2, 3, 5, 3, 4, 1]
lst.append(19)
print(lst)
>>> [1, 2, 3, 5, 3, 4, 1, 19]

• 리스트(파이썬)의 제일 마지막에 값을 추가한다.
• 길이가 얼마나 길던, 제일 마지막 인덱스에 추가하기 때문에 소요시간은 O(1)

pop

lst = [1, 2, 3, 5, 3, 4, 1]
print(lst.pop())
print(lst)
>>> 1
>>> [1, 2, 3, 5, 3, 4]

• 리스트(파이썬)의 제일 마지막의 값을 꺼내온다.
• 꺼내오는 개념이기 때문에, lst.pop()은 "pop하기 전 상태 lst의 가장 마지막 값"을 반환하며, lst의 상태를 수정한다.
  * print(lst.pop()) 참조
• 리스트객체.pop() 은 가장 마지막 인덱스에만 접근하기 때문에 소요시간은 O(1)
• 다만 리스트객체.pop(2) 이런식으로 사용할경우 중간 인덱스의 값을 지우고 그 뒤의 값들을 앞으로 땡겨와야 하기 때문에 결국 전체 인덱스를 돌아야 한다. >>> 이경우 BigO notation은 O(n)

  중간 인덱스의 값을 pop 하는 과정은 다음과 같다.
  

insert

lst = [1,2,3,4,5]
lst.insert(0,999)
print(lst)
>>> [999,1,2,3,4,5]

• 리스트의 특정 인덱스에 값을 추가한다.

1. 추가하려는 인덱스 뒤의 애들을 하나씩 뒤로 밀고 * 이떄 마지막 인덱스까지 돌면서 한칸씩 밀게 됨
2. 추가하려는 인덱스에 빈공간이 생기게 되니, 거기에 값을 추가함
   

• 모든 인덱스를 돌며 뒤로 한칸씩 미뤄야 하기 떄문에 소요시간은 O(n)

del

lst = [1,2,3,4,5]
del(lst[2])
print(lst)
>>> [1,2,4,5]

• 리스트의 특정 인덱스의 값을 삭제한다.

1. 삭제하려는 인덱스에 접근하여 해당 값을 삭제하고
2. 그 인덱스 뒤에 있는 애들을 한칸씩 땡긴다.

• 모든 인덱스를 돌며 앞으로 한칸씩 땡겨줘야 하기 때문에 소요시간은 O(n)

결론