Ruby의 배열에는 shift와 unshift 메소드가 있다

Ruby의 Array class를 보면 shift와 unshift 메소드를 제공한다.

arr = [1, 2, 3, 4, 5]

arr.shift # 1
arr.shift # 2

print arr # [3, 4, 5]
puts

arr.unshift 2
arr.unshift 1

print arr # [1, 2, 3, 4, 5]
puts

shift 메소드는 배열의 첫 번째 원소를 제거하고 해당 값을 반환한다. 그리고 남아있는 원소들은 한 칸씩 앞으로 당겨진다.

“Removes the first element of self and returns it (shifting all other elements down by one). Returns nil if the array is empty.” - Class: Array (Ruby 2.6.7) ↗

unshift 메소드는 shfit와 정확히 반대되는 개념으로, 새로운 값을 배열 첫 번째 위치에 삽입한다. 기존에 있던 원소들은 한 칸씩 뒤로 밀려난다.

“Prepends objects to the front of self, moving other elements upwards.” - Class: Array (Ruby 2.6.7) ↗

값이 삭제되거나 삽입될 때, 기존에 있던 모든 원소들이 앞으로 당겨지거나 뒤로 밀려나기 때문에 shftt와 unshift 메소드의 시간복잡도는 O(n)이 된다.

일반적으로 배열에서의 삽입과 삭제가 느린 이유 역시 위와 같은 원리로 동작하기 때문이다. 삽입과 삭제가 배열 마지막 위치에서 일어나는게 아닌 이상, shifting 과정이 필요하게 된다.

확장 🌱

• 메모리 상에 연속적으로 배치되지만 첫 원소만 포인터로 접근 가능하다면, lookup과 shift/unshift 모두 O(1)이 될 수 있다. 이런 구조의 자료구조가 존재할까?
• shift와 unshift로 머리가 top인 Stack을 구현할 수 있다
  • push와 pop을 사용하면 꼬리가 top이 된다
  • shift와 push를 사용하면 Queue를 구현할 수 있다

관련 노트 📘

• 250512043750 - 배열의 삽입과 삭제에는 O(n)의 시간이 필요하다