1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from collections import deque
queue = deque()
queue.append("Mary")  # O(1)
queue.append("John")
queue.append("Susan") # deque(['Mary', 'John', 'Susan'])
queue.popleft()       # deque(['John', 'Susan'])

history = deque()
history.appendleft(1)
history.appendleft(2)
history.appendleft(3) # deque([3,2,1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

'''
def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next
'''

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return self.data

class LinkedList:
    def __init__(self):
        self.head = None

    def __repr__(self): # representation
        node = self.head
        nodes = []
        while node is not None:
            nodes.append(node.data)
            node = node.next
        nodes.append("None")
        return " -> ".join(nodes)
    
    def add_first(self, node): # insert at the front
        node.next = self.head
        self.head = node     
    
    def add_last(self, node): # append at the end
        if self.head is None:
            self.head = node
            return
        for current_node in self:
            pass
        current_node.next = node
    
    def add_after(self, target_node_data, new_node): # insert after an existing node
        if self.head is None:
            raise Exception("List is empty")
    
        for node in self:
            if node.data == target_node_data:
                new_node.next = node.next
                node.next = new_node
                return
    
        raise Exception("Node with data '%s' not found" % target_node_data)
        
    def add_before(self, target_node_data, new_node): # insert before an existing node
        if self.head is None:
            raise Exception("List is empty")

        if self.head.data == target_node_data:
            return self.add_first(new_node)

        prev_node = self.head
        for node in self:
            if node.data == target_node_data:
                prev_node.next = new_node
                new_node.next = node
                return
            prev_node = node
    
        raise Exception("Node with data '%s' not found" % target_node_data)

    def remove_node(self, target_node_data): # remove
        if self.head is None:
            raise Exception("List is empty")
    
        if self.head.data == target_node_data:
            self.head = self.head.next
            return
    
        previous_node = self.head
        for node in self:
            if node.data == target_node_data:
                previous_node.next = node.next
                return
            previous_node = node
    
        raise Exception("Node with data '%s' not found" % target_node_data) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Create
LinkedList<Integer> ll = new LinkedList<>();

// Add - O(1)
ll.add(1);
ll.add(2);
ll.add(3);

// Access - O(N)
int elem = ll.get(0); // 1

// Search - O(N)
int id = ll.indexOf(3); // 2

// Update - O(N)
ll.set(2,100); // [1,2,100]

// Remove - O(N)
ll.remove(1); // [1,100]

// size
int length = ll.size();