# How to use "deque" for Python data

## Introduction

I got a good question when using deque in the D question of "At Coder Beginner Contest 158" held the other day, so I would like to summarize how to use it in Python.

## What is a deque

A type of Python container data type. Data can be added at the cost of O (1) for both the beginning and the end. If it is a normal list, it can be implemented at the cost of O (n) when adding it to the beginning.

This is useful when you want to add data not only at the end but also at the beginning.

## Method introduction

### Add data to the end append

Use the "append" method as you would a List.

### Add data to the beginning appendleft

Use the "append left" method. List uses the "insert" method.

### Sample code 1

``````from collections import deque

d = deque('a')
d.append('b')
d.appendleft('c')

print(d)
# -> deque(['c', 'a', 'b'])

print(''.join(d))
# -> cab
``````

### Shallow copy copy

Make a shallow copy of the deque. See below for shallow copies.

copy --- Shallow copy and deep copy operations https://docs.python.org/ja/3/library/copy.html

### Sample code 2

``````from collections import deque

d1 = deque([1, 2, 3, 4, 5])
d2 = d1.copy()

print(d1)
# -> deque([1, 2, 3, 4, 5])
print(d2)
# -> deque([1, 2, 3, 4, 5])

d1.append(6)

print(d1)
# -> deque([1, 2, 3, 4, 5, 6])
print(d2)
# -> deque([1, 2, 3, 4, 5])
``````

### Enumeration of elements count

Count the number of values equal to the arguments in the deque.

### Element position index

Returns a position with a value equal to the argument in the deque. If not found, raise a ValueError.

### Extracting elements pop pop left

Deletes the element to the right of pop: deque and returns it. Deletes the element on the left side of popleft: deque and returns it.

### Remove element remove

Remove the first value equal to the argument in the deque. If not found, raise a ValueError.

### Element reversal reverse

Invert the order of the elements in the deque.

### Sample code 3

``````from collections import deque

d = deque([1, 2, 3, 4, 5])

d.insert(2, 5)
print(d)
# -> deque([1, 2, 5, 3, 4, 5])

print(d.count(5))
# -> 2

print(d.index(2))
# -> 1
print(d.index(5))
# -> 2
print(d.index(5, 4, 6))
# -> 5

print(d.pop())
# -> 5
print(d)
# -> deque([1, 2, 5, 3, 4])
print(d.popleft())
# -> 1
print(d)
# -> deque([2, 5, 3, 4])
d.remove(5)
print(d)
# -> deque([2, 3, 4])

d.reverse()
print(d)
# -> deque([4, 3, 2])
``````

Add an interactive element to the right.

### Add iterable element to the left extendleft

Add an interactive element to the left.

### Shift elements rotate

Moves the element to the right by the value of the argument. Elements beyond the end move to the beginning. If you specify a negative number, it moves to the left.

### Sample code 4

``````from collections import deque

d = deque([1, 2, 3, 4, 5])

li = [6,7,8,9]
d.extend(li)
print(d)
# -> deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

d.extendleft(li)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])

d.rotate(1)
print(d)
# -> deque([9, 9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8])

d.rotate(-1)
print(d)
# -> deque([9, 8, 7, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9])

d.clear()
print(d)
# -> deque([])
``````

### Maximum length specification maxlen

Specify the maximum number of elements of deque. If you add more than the maximum number of elements, the element on the opposite side will be deleted.

### Sample code 5

``````from collections import deque

li = [1, 2, 3, 4, 5]
d = deque(li, 3)
print(d)
# ->deque([3, 4, 5], maxlen=3)

d2 = deque([], 3)
for i in range(10):
d2.append(i)
print(d2)
# -> deque([7, 8, 9], maxlen=3)
``````

## List and performance comparison

(I am doing it with the feeling of trying it) The performance was compared by simply adding the value to the right if it was an even number and to the left if it was an odd number 1,000,000 times. List was about 147 seconds and deque was about 0.3 seconds.

``````from collections import deque
import time

start = time.time()
li = []
for i in range(1000000):
if i % 2 == 0:
li.append(i)
else:
li.insert(0, i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 147.49888038635254

start = time.time()
d = deque([])
for i in range(1000000):
if i % 2 == 0:
d.append(i)
else:
d.appendleft(i)
elapsed_time = time.time() - start
print(elapsed_time)
# -> 0.3092050552368164
``````

## Impressions

I didn't know the deque in the contest, so I created a List with twice the maximum number of elements and added the first element in the middle to handle it. I think it would be easier to solve if I knew the deque, so I wanted to learn the data structure well.

Even if I understand the amount of calculation, I thought that there would be no difference when actually comparing the processing times.

## reference

collections --- container data type https://docs.python.org/ja/3/library/collections.html#collections.deque

Data type collections.deque that can be used as a "double-ended queue" in Python https://kakakakakku.hatenablog.com/entry/2019/01/04/214907

[Python] Measures and displays the time required for processing https://qiita.com/fantm21/items/3dc7fbf4e935311488bc