2. Doubly Linked List

In [1]:

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

    def __repr__(self):
        return "<Node: %s>" % self.data

class Node: def __init__(self, data, next_node=None, prev_node=None): self.data = data self.prev = prev_node self.next = next_node def __repr__(self): return "" % self.data

In [2]:

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.__count = 0

    def __len__(self):
        return self.__count

    def __iter__(self):
        current = self.head
        while current != None:
            yield current.data
            current = current.next

    def is_empty(self):
        return self.head == None

    def is_empty_alt(self):
        if self.__count == 0 or self.head is None:
            print("List is empty")
        return

    def __repr__(self):
        current = self.head
        nodes = []
        while current != None:
            if current == self.head:
                nodes.append("[Head: %s]" % current.data)
            elif current.next == None:
                nodes.append("[Tail: %s]" % current.data)
            else:
                nodes.append("[%s]" % current.data)

            current = current.next

        return "->".join(nodes)

    def add_head(self, data):
        node = Node(data)
        if self.head == None:
            self.head = node
        else:
            self.head.prev = node
            node.next = self.head
            self.head = node

        self.__count += 1

    def add_head_alt(self, data):
        node = Node(data, next_node=self.head)

        if self.head == None:
            self.head = node
        else:
            self.head.prev = node
            self.head = node
        self.__count += 1

    def add_tail(self, data):
        node = Node(data)

        if self.head == None:
            self.head = node
        else:
            current = self.head
            while current.next != None:
                current = current.next

            current.next = node
            node.prev = current

        self.__count += 1

    def insert(self, data, index):
        if index < 0 or index > self.__count:
            print("Index out of bounds")
            return

        node = Node(data)
        pos = 0
        current = self.head
        previous = self.head

        while pos < index:
            previous = current
            current = current.next
            pos += 1

        print("pos: {}, index: {}".format(pos, index))
        print("previous: {}".format(previous))
        print("current: {}".format(current))

        if pos == 0 or self.head == None:
            print("Inserting => {} at head".format(data))
            node.next = self.head
            self.head = node
            # self.__count += 1

        elif current is None:
            print("Inserting => {} at tail".format(data))
            previous.next = node
            node.prev = previous
        else:
            print("Inserting => {} at zero-index pos: {}".format(data, pos))
            node.next = current
            node.prev = previous
            previous.next = node

        self.__count += 1
        print("Length of current list is : {}".format(self.__count))

    def node_at_index(self, index):
        if index < 0 or index >= self.__count:
            print("index out of bounds")
            return

        current = self.head
        pos = 0
        while pos < index:
            current = current.next
            pos += 1
        return current

    def search(self, key):
        if not self.is_empty():
            current = self.head
            found = False
            pos = 0
            while current is not None and not found:
                if key == current.data:
                    found = True
                    break
                pos += 1
                current = current.next

            if found:
                print("Found key: {} at postion: {}".format(key, pos))
            else:
                print("No node/element exists matching the given key: {}".format(key))

    def reverse(self):
        if self.__count == 0 or self.head is None:
            print("List is empty, nothing to reverse")
            return


## This method uses another variable previous but that is not required.
## Think of a way to solve this without that

#     def remove_key(self, key):

#         if self.__count < 0 or self.head == None:
#             print("Empty list")
#             return


#         previous = self.head
#         current = self.head
#         found = False

#         while current != None:
#             if current.data == key:
#                 found = True
#                 break
#             previous = current
#             current = current.next

#         if found:
#             if current == self.head:
#                 if current.next == None:
#                     print("only one element at head")
#                     self.head = None
#                     del current
#                     del previous
#                 else:
#                     print("at head but more elements present")
#                     self.head = current.next
#                     current.prev = None
#                     del current
#                     del previous

#             elif current.next == None and previous.next != None:
#                 print("element at tail")
#                 print("previous: ", previous)
#                 print("current: ", current)
#                 previous.next = None
#                 del current
#             else:
#                 print("middle?")
#                 previous.next = current.next
#                 current.next.prev = previous
#                 del current
#             self.__count -= 1
#         else:
#             print("Key: {} not found".format(key))

class DoublyLinkedList: def __init__(self): self.head = None self.__count = 0 def __len__(self): return self.__count def __iter__(self): current = self.head while current != None: yield current.data current = current.next def is_empty(self): return self.head == None def is_empty_alt(self): if self.__count == 0 or self.head is None: print("List is empty") return def __repr__(self): current = self.head nodes = [] while current != None: if current == self.head: nodes.append("[Head: %s]" % current.data) elif current.next == None: nodes.append("[Tail: %s]" % current.data) else: nodes.append("[%s]" % current.data) current = current.next return "->".join(nodes) def add_head(self, data): node = Node(data) if self.head == None: self.head = node else: self.head.prev = node node.next = self.head self.head = node self.__count += 1 def add_head_alt(self, data): node = Node(data, next_node=self.head) if self.head == None: self.head = node else: self.head.prev = node self.head = node self.__count += 1 def add_tail(self, data): node = Node(data) if self.head == None: self.head = node else: current = self.head while current.next != None: current = current.next current.next = node node.prev = current self.__count += 1 def insert(self, data, index): if index < 0 or index > self.__count: print("Index out of bounds") return node = Node(data) pos = 0 current = self.head previous = self.head while pos < index: previous = current current = current.next pos += 1 print("pos: {}, index: {}".format(pos, index)) print("previous: {}".format(previous)) print("current: {}".format(current)) if pos == 0 or self.head == None: print("Inserting => {} at head".format(data)) node.next = self.head self.head = node # self.__count += 1 elif current is None: print("Inserting => {} at tail".format(data)) previous.next = node node.prev = previous else: print("Inserting => {} at zero-index pos: {}".format(data, pos)) node.next = current node.prev = previous previous.next = node self.__count += 1 print("Length of current list is : {}".format(self.__count)) def node_at_index(self, index): if index < 0 or index >= self.__count: print("index out of bounds") return current = self.head pos = 0 while pos < index: current = current.next pos += 1 return current def search(self, key): if not self.is_empty(): current = self.head found = False pos = 0 while current is not None and not found: if key == current.data: found = True break pos += 1 current = current.next if found: print("Found key: {} at postion: {}".format(key, pos)) else: print("No node/element exists matching the given key: {}".format(key)) def reverse(self): if self.__count == 0 or self.head is None: print("List is empty, nothing to reverse") return ## This method uses another variable previous but that is not required. ## Think of a way to solve this without that # def remove_key(self, key): # if self.__count < 0 or self.head == None: # print("Empty list") # return # previous = self.head # current = self.head # found = False # while current != None: # if current.data == key: # found = True # break # previous = current # current = current.next # if found: # if current == self.head: # if current.next == None: # print("only one element at head") # self.head = None # del current # del previous # else: # print("at head but more elements present") # self.head = current.next # current.prev = None # del current # del previous # elif current.next == None and previous.next != None: # print("element at tail") # print("previous: ", previous) # print("current: ", current) # previous.next = None # del current # else: # print("middle?") # previous.next = current.next # current.next.prev = previous # del current # self.__count -= 1 # else: # print("Key: {} not found".format(key))

In [3]:

dl = DoublyLinkedList()

dl = DoublyLinkedList()

In [4]:

for i in range(0, 4):
    dl.add_head_alt(i)

for i in range(0, 4): dl.add_head_alt(i)

In [5]:

len(dl)

len(dl)

Out[5]:

4

In [6]:

for i in dl:
    print(i)

for i in dl: print(i)

3
2
1
0

In [7]:

dl

dl

Out[7]:

[Head: 3]->[2]->[1]->[Tail: 0]

In [8]:

len(dl)

len(dl)

Out[8]:

4

In [9]:

dl.insert(10, 10)

dl.insert(10, 10)

Index out of bounds

In [10]:

dl.insert(data=100, index=0)

dl.insert(data=100, index=0)

pos: 0, index: 0
previous: <Node: 3>
current: <Node: 3>
Inserting => 100 at head
Length of current list is : 5

In [11]:

dl

dl

Out[11]:

[Head: 100]->[3]->[2]->[1]->[Tail: 0]

In [12]:

len(dl)

len(dl)

Out[12]:

5

In [13]:

dl.insert(data=500, index=5)

dl.insert(data=500, index=5)

pos: 5, index: 5
previous: <Node: 0>
current: None
Inserting => 500 at tail
Length of current list is : 6

In [14]:

dl

dl

Out[14]:

[Head: 100]->[3]->[2]->[1]->[0]->[Tail: 500]

In [15]:

dl.insert(data=1000, index=4)

dl.insert(data=1000, index=4)

pos: 4, index: 4
previous: <Node: 1>
current: <Node: 0>
Inserting => 1000 at zero-index pos: 4
Length of current list is : 7

In [16]:

dl

dl

Out[16]:

[Head: 100]->[3]->[2]->[1]->[1000]->[0]->[Tail: 500]

In [17]:

dl.insert(data=-1, index=6)

dl.insert(data=-1, index=6)

pos: 6, index: 6
previous: <Node: 0>
current: <Node: 500>
Inserting => -1 at zero-index pos: 6
Length of current list is : 8

In [18]:

len(dl)

len(dl)

Out[18]:

8

In [19]:

dl

dl

Out[19]:

[Head: 100]->[3]->[2]->[1]->[1000]->[0]->[-1]->[Tail: 500]

In [20]:

dl.reverse()

dl.reverse()

In [21]:

dl

dl

Out[21]:

[Head: 100]->[3]->[2]->[1]->[1000]->[0]->[-1]->[Tail: 500]

In [22]:

len(dl)

len(dl)

Out[22]:

8

In [23]:

dl.node_at_index(7)

dl.node_at_index(7)

Out[23]:

<Node: 500>

In [24]:

dl.node_at_index(0)

dl.node_at_index(0)

Out[24]:

<Node: 100>

In [25]:

dl.node_at_index(8)

dl.node_at_index(8)

index out of bounds

In [26]:

dl.node_at_index(1)

dl.node_at_index(1)

Out[26]:

<Node: 3>

In [27]:

dl.search(500)

dl.search(500)

Found key: 500 at postion: 7

In [28]:

dl.search(100)

dl.search(100)

Found key: 100 at postion: 0

In [29]:

dl.search(0)

dl.search(0)

Found key: 0 at postion: 5

In [30]:

dl.search(2000)

dl.search(2000)

No node/element exists matching the given key: 2000

Remove element¶

In [31]:

dl

dl

Out[31]:

[Head: 100]->[3]->[2]->[1]->[1000]->[0]->[-1]->[Tail: 500]

In [32]:

dl.remove(1)

dl.remove(1)

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In [32], line 1
----> 1 dl.remove(1)

AttributeError: 'DoublyLinkedList' object has no attribute 'remove'

In [ ]:

dl

dl

In [ ]:

dl.remove(500)

dl.remove(500)

In [ ]:

dl

dl

In [ ]:

dl.remove_key(100)

dl.remove_key(100)

In [ ]:

dl

dl

In [ ]:

In [ ]:

In [ ]:

In [ ]:

Remove element from index¶

In [ ]:

# dl.remove_at_index(0)

# dl

# dl.remove_at_index(3)

# dl

# dl.remove_at_index(4)

# len(dl)

# dl.remove_at_index(0)

# dl

# dl.remove_at_index(1)

# dl

# dl.remove_at_index(0)

# len(dl)

# dl.remove_element(1)

# len(dl)

# dl

# dl.remove_at_index(0) # dl # dl.remove_at_index(3) # dl # dl.remove_at_index(4) # len(dl) # dl.remove_at_index(0) # dl # dl.remove_at_index(1) # dl # dl.remove_at_index(0) # len(dl) # dl.remove_element(1) # len(dl) # dl

In [ ]:

dl = DoublyLinkedList()

dl = DoublyLinkedList()

In [ ]:

dl.add_head(5)
dl.add_head(4)

dl.add_head(5) dl.add_head(4)

In [ ]:

dl

dl

In [ ]:

dl.remove_key(5)

dl.remove_key(5)

In [ ]:

dl.remove_key(500)

dl.remove_key(500)

In [ ]:

dl.remove_key(1)

dl.remove_key(1)

In [ ]: