# linear data structure made up of nodes and refs to the next node
# lets make some node class
class Node:
def __init__(self, value, next_node = None):
# value that the node is holding
self.
A Linked List is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.
Each element of a doubly linked list is an object with an attribute key and two other pointer attributes next and prev.
A list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not.
Given a linked list, in addition to the next pointer, each node has a child pointer that can point to a separate list. With the head node, flatten the list to a single-level linked list.
Reverse a singly linked list. Implement it recursively and iteratively.
are a sequential collection of data that uses relational pointers on each data node to link to the next node in the list.
Unlike arrays, linked lists do not have objective positions in the list. Instead, they have relational positions based on their surrounding nodes.
The first node in a linked list is called the head node, and the final is called the tail node, which has a null pointer.
Linked lists can be singly or doubly linked depending if each node has just a single pointer to the next node or if it also has a second pointer to the previous node.
You can think of linked lists like a chain; individual links only have a connection to their immediate neighbors but all the links together form a larger structure.
Python does not have a built-in implementation of linked lists and therefore requires that you implement a Node class to hold a data value and one or more pointers.
Advantages:
Efficient insertion and deletion of new elements
Simpler to reorganize than arrays
Useful as a starting point for advanced data structures like graphs or trees
Disadvantages:
Storage of pointers with each data point increases memory usage
Must always traverse the linked list from Head node to find a specific element
Applications:
Building block for advanced data structures
Solutions that call for frequent addition and removal of data
Print the middle element of a given linked list
Remove duplicate elements from a sorted linked list
Check if a singly linked list is a palindrome
Merge K sorted linked lists
A linked list is similar to an array, it holds values. However, links in a linked list do not have indexes.
This is an example of a double ended, doubly linked list.
Each link references the next link and the previous one.
A Doubly Linked List (DLL) contains an extra pointer, typically called previous
pointer, together with next pointer and data which are there in singly linked list.
Test:
"""
Each ListNode holds a reference to its previous node
as well as its next node in the List.
"""
class ListNode:
def __init__(self, value, prev=None, next=None):
self.prev = prev
self.value = value
self.next = next
"""
Our doubly-linked list class. It holds references to
the list's head and tail nodes.
"""
class DoublyLinkedList:
def __init__(self, node=None):
self.head = node
self.tail = node
self.length = 1 if node is not None else 0
def __len__(self):
return self.length
"""
Wraps the given value in a ListNode and inserts it
as the new head of the list. Don't forget to handle
the old head node's previous pointer accordingly.
"""
def add_to_head(self, value):
# wrap the input value in a node
new_node = ListNode(value)
# increment the length
self.length += 1
# check if the linked list is empty
if not self.head and not self.tail:
# if the list is initially empty, set both head and tail to the new node
self.head = new_node
self.tail = new_node
# we have a non-empty list, add the new node to the head
else:
# set the new node's `next` to refer to the current head
new_node.next = self.head
# set the current head's 'prev' to refer to the new_node (added to make it work with DLL)
self.head.prev = new_node
# set the list's head reference to the new node
self.head = new_node
"""
Removes the List's current head node, making the
current head's next node the new head of the List.
Returns the value of the removed Node.
"""
def remove_from_head(self):
value = self.head.value
self.delete(self.head)
return value
"""
Wraps the given value in a ListNode and inserts it
as the new tail of the list. Don't forget to handle
the old tail node's next pointer accordingly.
"""
def add_to_tail(self, value):
new_node = ListNode(value, None, None)
self.length += 1
if not self.tail and not self.head:
self.tail = new_node
self.head = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
"""
Removes the List's current tail node, making the
current tail's previous node the new tail of the List.
Returns the value of the removed Node.
"""
def remove_from_tail(self):
value = self.tail.value
self.delete(self.tail)
return value
"""
Removes the input node from its current spot in the
List and inserts it as the new head node of the List.
"""
def move_to_front(self, node):
if node is self.head:
return
value = node.value
if node is self.tail:
self.remove_from_tail()
else:
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
self.length -= 1
self.add_to_head(value)
"""
Removes the input node from its current spot in the
List and inserts it as the new tail node of the List.
"""
def move_to_end(self, node):
if node is self.tail:
return
value = node.value
if node is self.head:
self.remove_from_head()
else:
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
self.length -= 1
self.add_to_tail(value)
"""
Deletes the input node from the List, preserving the
order of the other elements of the List.
"""
def delete(self, node):
if not self.head and not self.tail:
return
if self.head is self.tail:
self.head = None
self.tail = None
elif self.head is node:
self.head = node.next
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
elif self.tail is node:
self.tail = node.prev
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
else:
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
self.length -= 1
"""
Finds and returns the maximum value of all the nodes
in the List.
"""
def get_max(self):
if not self.head:
return None
max_val = self.head.value
current = self.head
while current:
if current.value > max_val:
max_val = current.value
current = current.next
return max_valimport unittest
from doubly_linked_list import ListNode
from doubly_linked_list import DoublyLinkedList
class DoublyLinkedListTests(unittest.TestCase):
def setUp(self):
self.node = ListNode(1)
self.dll = DoublyLinkedList(self.node)
def test_list_remove_from_tail(self):
self.dll.remove_from_tail()
self.assertIsNone(self.dll.head)
self.assertIsNone(self.dll.tail)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_tail(33)
self.assertEqual(self.dll.head.value, 33)
self.assertEqual(self.dll.tail.value, 33)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_tail(), 33)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_tail(68)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_tail(), 68)
self.assertEqual(len(self.dll), 0)
def test_list_remove_from_head(self):
self.dll.remove_from_head()
self.assertIsNone(self.dll.head)
self.assertIsNone(self.dll.tail)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_head(2)
self.assertEqual(self.dll.head.value, 2)
self.assertEqual(self.dll.tail.value, 2)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_head(), 2)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_head(55)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_head(), 55)
self.assertEqual(len(self.dll), 0)
def test_list_add_to_tail(self):
self.assertEqual(self.dll.tail.value, 1)
self.assertEqual(len(self.dll), 1)
self.dll.add_to_tail(30)
self.assertEqual(self.dll.tail.prev.value, 1)
self.assertEqual(self.dll.tail.value, 30)
self.assertEqual(len(self.dll), 2)
self.dll.add_to_tail(20)
self.assertEqual(self.dll.tail.prev.value, 30)
self.assertEqual(self.dll.tail.value, 20)
self.assertEqual(len(self.dll), 3)
def test_list_add_to_head(self):
self.assertEqual(self.dll.head.value, 1)
self.dll.add_to_head(10)
self.assertEqual(self.dll.head.value, 10)
self.assertEqual(self.dll.head.next.value, 1)
self.assertEqual(len(self.dll), 2)
def test_list_move_to_end(self):
self.dll.add_to_head(40)
self.assertEqual(self.dll.tail.value, 1)
self.assertEqual(self.dll.head.value, 40)
self.dll.move_to_end(self.dll.head)
self.assertEqual(self.dll.tail.value, 40)
self.assertEqual(self.dll.tail.prev.value, 1)
self.assertEqual(len(self.dll), 2)
self.dll.add_to_tail(4)
self.dll.move_to_end(self.dll.head.next)
self.assertEqual(self.dll.tail.value, 40)
self.assertEqual(self.dll.tail.prev.value, 4)
self.assertEqual(len(self.dll), 3)
def test_list_move_to_front(self):
self.dll.add_to_tail(3)
self.assertEqual(self.dll.head.value, 1)
self.assertEqual(self.dll.tail.value, 3)
self.dll.move_to_front(self.dll.tail)
self.assertEqual(self.dll.head.value, 3)
self.assertEqual(self.dll.head.next.value, 1)
self.assertEqual(len(self.dll), 2)
self.dll.add_to_head(29)
self.dll.move_to_front(self.dll.head.next)
self.assertEqual(self.dll.head.value, 3)
self.assertEqual(self.dll.head.next.value, 29)
self.assertEqual(len(self.dll), 3)
def test_list_delete(self):
self.dll.delete(self.node)
self.assertIsNone(self.dll.head)
self.assertIsNone(self.dll.tail)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_tail(1)
self.dll.add_to_head(9)
self.dll.add_to_tail(6)
self.dll.delete(self.dll.head.next)
self.assertEqual(self.dll.head.value, 9)
self.assertEqual(self.dll.head.next, self.dll.tail)
self.assertEqual(self.dll.tail.value, 6)
self.dll.delete(self.dll.head)
self.assertEqual(self.dll.head.value, 6)
self.assertEqual(self.dll.tail.value, 6)
self.assertEqual(len(self.dll), 1)
self.dll.delete(self.dll.head)
self.assertIsNone(self.dll.head)
self.assertIsNone(self.dll.tail)
self.assertEqual(len(self.dll), 0)
def test_get_max(self):
self.assertEqual(self.dll.get_max(), 1)
self.dll.add_to_tail(100)
self.assertEqual(self.dll.get_max(), 100)
self.dll.add_to_tail(55)
self.assertEqual(self.dll.get_max(), 100)
self.dll.add_to_tail(101)
self.assertEqual(self.dll.get_max(), 101)
if __name__ == '__main__':
unittest.main()Implement an LRU cache with O(1) runtime for all its operations.
Check distance between values in linked list.
A question involving an API's integration with hash map where the buckets of hash map are made up of linked lists.
Given a singly linked list (a list which can only be traversed in one direction), find the item that is located at 'k' items from the end. So if the list is a, b, c, d and k is 2 then the answer is 'c'. The solution should not search the list twice.
How can you tell if a Linked List is a Palindrome?
Find the intersection point of two linked lists
Advantages over SLL - It can be traversed in both forward and backward direction.
Delete operation is more efficient
"""
First the Node class needs to be created because every item in a linked list
is a node item containing the data and the pointer to the node it links to
"""
class Node:
def __init__(self, data):
self.data = data
self.nextNode = None
"""
Next the linked list can be created and initialized with the head as none
because it doesn't exist yet and the number of nodes to 0 because its empty
"""
class LinkedList:
def __init__(self):
self.head = None
self.numOfNodes = 0
"""
Functions for the LinkedList class:
"""
# function to insert a new node at the beginning of the list O(1)
def insert_start(self, data):
# first increase the number of nodes by 1
self.numOfNodes = self.numOfNodes + 1
# then insert the data into the new node
new_node = Node(data)
# check to see if there is a head
if not self.head:
# if not create it with the new node
self.head = new_node
# if there is a head
else:
# set the pointer of the new node to the old head
new_node.nextNode = self.head
# set the new node as the new head of the list
self.head = new_node
# function to insert a new node at the end of the list O(N)
def insert_end(self, data):
# first increase the number of nodes by 1
self.numOfNodes = self.numOfNodes + 1
# then insert the data into the new node
new_node = Node(data)
# get a reference to the head node to begin iteration
actual_node = self.head
# iterate the node looking for the node that points to Null
while actual_node.nextNode is not None:
# if not the last node pointing to Null
# change active_node to the next node its pointing to
actual_node = actual_node.nextNode
# when we find the node that is pointing to Null
# change its pointer to point to the new node
actual_node.nextNode = new_node
# function to get the size of the linked list O(1)
def size_of_list(self):
# return the number of nodes the list contains
return self.numOfNodes
# function to traverse the linked list and print all of its nodes data
def traverse(self):
# set the reference to the first node
actual_node = self.head
# iterate the list while the referenced node is not Null
while actual_node is not None:
# print out the actual_node data value
print(actual_node.data)
# move the reference to the next node in the list
actual_node = actual_node.nextNode
# function to remove a node from the list O(N)
def remove(self, data):
# if the list is empty return
if self.head is None:
return
# set the reference to the first node
actual_node = self.head
# set the reference to the previous node which is none at first
previous_node = None
# iterate the list continuing while the actual_node doesn't contain
# what we're looking for and isn't Null (empty list or end of list)
while actual_node is not None and actual_node.data != data:
# consider the next node in the list
# iterate the prev node to current
previous_node = actual_node
# iterate the actual node to the next
actual_node = actual_node.nextNode
# if we reach the end of the list and don't find a match return
if actual_node is None:
return
# at this point we have found a match
# first decrease the number of items in the list
self.numOfNodes -= 1
# after the while loop ( the node with the data was found)
# if the previous node is Null then the head node is the one to remove
if previous_node is None:
# setting the new head to be the next node will remove the current
# actual node
self.head = actual_node.nextNode
# if previous node is not Null
else:
# set the prev.nextNode to be the actual nextNode cutting out the
# actual node we want to remove
previous_node.nextNode = actual_node.nextNode
"""
use the functions just created
"""
# create a new LinkedList
linked_list = LinkedList()
# insert a few nodes at the beginning of the list O(1)
linked_list.insert_start(4)
linked_list.insert_start(3)
linked_list.insert_start(7)
# insert a node at the end of the list O(N)
linked_list.insert_end(10)
# remove a node from list O(N)
linked_list.remove(3)
# print the node values of the list O(N)
linked_list.traverse()
# print the size of the list
print(f'size: {linked_list.size_of_list()}')
# Singly-Linked List
#
# The linked list is passed around as a variable pointing to the
# root node of the linked list, or None if the list is empty.
class LinkedListNode:
def __init__(self, value):
self.value = value
self.next = None
def linked_list_append(linked_list, value):
'''Appends a value to the end of the linked list'''
node = linked_list
insert_node = LinkedListNode(value)
if not node:
return insert_node
while node.next:
node = node.next
node.next = insert_node
return linked_list
def linked_list_insert_index(linked_list, value, index):
'''Inserts a value at a particular index'''
node = linked_list
insert_node = LinkedListNode(value)
# Check if inserting at head
if index == 0:
insert_node.next = node
return insert_node
# Skip ahead
for _ in range(index - 1):
node = node.next
if not node:
raise ValueError
insert_node.next = node.next
node.next = insert_node
return linked_list
def linked_list_delete(linked_list, value):
'''Deletes the first occurrence of a value in the linked list'''
node = linked_list
# Check if deleting at head
if node.value == value:
return node.next
# Skip ahead
while node.next:
if node.next.value == value:
node.next = node.next.next
return linked_list
node = node.next
raise ValueError
def linked_list_delete_index(linked_list, index):
'''Deletes the element at a particular index in the linked list'''
node = linked_list
# Check if deleting at head
if index == 0:
return node.next
# Skip ahead
for _ in range(index - 1):
node = node.next
if not node:
raise ValueError
if not node.next:
raise ValueError
node.next = node.next.next
return linked_list
def linked_list_iter(linked_list):
'''Lazy iterator over each node in the linked list'''
node = linked_list
while node is not None:
yield node
node = node.next
# Append to back
linked_list = None # Start with an empty linked list
linked_list = linked_list_append(linked_list, 1)
linked_list = linked_list_append(linked_list, 2)
linked_list = linked_list_append(linked_list, 4)
print([node.value for node in linked_list_iter(linked_list)])
# Insert by index
linked_list = linked_list_insert_index(linked_list, 0, 0) # Front
print([node.value for node in linked_list_iter(linked_list)])
linked_list = linked_list_insert_index(linked_list, 3, 3) # Back
print([node.value for node in linked_list_iter(linked_list)])
# Delete "3"
linked_list = linked_list_delete(linked_list, 3)
print([node.value for node in linked_list_iter(linked_list)])
# Delete by index
linked_list = linked_list_delete_index(linked_list, 0)
print([node.value for node in linked_list_iter(linked_list)])
linked_list = linked_list_delete_index(linked_list, 1)
print([node.value for node in linked_list_iter(linked_list)])
# Delete until empty
linked_list = linked_list_delete_index(linked_list, 0)
linked_list = linked_list_delete_index(linked_list, 0)
print([node.value for node in linked_list_iter(linked_list)])
[1, 2, 4]
[0, 1, 2, 4]
[0, 1, 2, 3, 4]
[0, 1, 2, 4]
[1, 2, 4]
[1, 4]
[]"""The LinkedList code from before is provided below.
Add three functions to the LinkedList.
"get_position" returns the element at a certain position.
The "insert" function will add an element to a particular
spot in the list.
"delete" will delete the first element with that
particular value.
Then, use "Test Run" and "Submit" to run the test cases
at the bottom."""
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def append(self, new_element):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def get_position(self, position):
"""Get an element from a particular position.
Assume the first position is "1".
Return "None" if position is not in the list."""
current = self.head
if(self.head):
for i in range(position)[1:]:
if(current.next==None):
return None
else:
current=current.next
return current
return None
def insert(self, new_element, position):
"""Insert a new node at the given position.
Assume the first position is "1".
Inserting at position 3 means between
the 2nd and 3rd elements."""
current = self.head
if(self.head):
for i in range(position)[1:]:
if(i==position-1):
after = current.next
current.next = new_element
new_element.next = after
elif(current.next!=None):
current = current.next
else:
return 'position out of bounds'
pass
def delete(self, value):
"""Delete the first node with a given value."""
current = self.head
if(self.head):
while(current.next!=None):
if(current.next.value==value):
after = current.next.next
current.next = after
else:
current = current.next
if(self.head.value==value):
after = self.head.next
self.head = after
pass
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
# Start setting up a LinkedList
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)
# Test get_position
# Should print 3
print ll.head.next.next.value
# Should also print 3
print ll.get_position(3).value
# Test insert
ll.insert(e4,3)
# Should print 4 now
print ll.get_position(3).value
# Test delete
ll.delete(1)
# Should print 2 now
print ll.get_position(1).value
# Should print 4 now
print ll.get_position(2).value
# Should print 3 now
print ll.get_position(3).value
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
from __future__ import annotations
from collections.abc import Iterable, Iterator
from typing import Optional
from graph_examples.linked_lists.base_lists import (
BaseCircularLinkedList,
BaseLinearLinkedList,
BaseDoublyLinkedList,
BaseSinglyLinkedList,
)
from graph_examples.linked_lists.nodes import LinkedNode, DoublyLinkedNode, CircularLinkedNode, CircularDoublyLinkedNode
from graph_examples.linked_lists.base_nodes import T
class LinkedList(BaseLinearLinkedList[T], BaseSinglyLinkedList[T]):
def __init__(self, values: Iterable[T] = ()) -> None:
values_iter = iter(values)
try:
self.head = LinkedNode(next(values_iter))
except StopIteration:
self.head = None
node = self.head
for value in values_iter:
node.next = LinkedNode(value)
node = node.next
def appendleft(self, value: T) -> None:
self.head = LinkedNode(value, self.head)
def popleft(self) -> T:
if not self:
raise IndexError
node = self.head
self.head = node.next
return node.value
def reverse(self) -> None:
node = self.head
last_node = None
while node is not None:
node.next, last_node, node = last_node, node, node.next
self.head = last_node
class DoublyLinkedList(BaseLinearLinkedList[T], BaseDoublyLinkedList[T]):
def __init__(self, values: Iterable = ()) -> None:
values_iter = iter(values)
try:
self.head = DoublyLinkedNode(next(values_iter))
except StopIteration:
self.head = None
node = self.head
for value in values_iter:
node.next = DoublyLinkedNode(value, None, node)
node = node.next
self.tail = node
def __reversed__(self) -> Iterator[T]:
node = self.tail
while node is not None:
yield node.value
node = node.last
def append(self, value: T):
old_tail = self.tail
self.tail = DoublyLinkedNode(value, None, old_tail)
if old_tail is None:
self.head = self.tail
else:
old_tail.next = self.tail
def appendleft(self, value: T):
old_head = self.head
self.head = DoublyLinkedNode(value, old_head)
if old_head is None:
self.tail = self.head
else:
old_head.last = self.head
def pop(self) -> T:
if not self:
raise IndexError
old_tail = self.tail
self.tail = old_tail.last
if self.tail is None:
self.head = None
else:
self.tail.next = None
return old_tail.value
def popleft(self) -> T:
if not self:
raise IndexError
old_head = self.head
self.head = old_head.next
if self.head is None:
self.tail = None
else:
self.head.last = None
return old_head.value
def reverse(self) -> None:
node = self.head
self.head, self.tail = self.tail, self.head
while node is not None:
node.next, node.last, node = node.last, node.next, node.next
class CircularLinkedList(BaseCircularLinkedList[T], BaseSinglyLinkedList[T]):
def __init__(self, values: Iterable[T] = ()):
values_iter = iter(values)
try:
head = CircularLinkedNode(next(values_iter))
except StopIteration:
head = None
node = head
for value in values_iter:
node.next = CircularLinkedNode(value, head)
node = node.next
self.tail = node
@property
def head(self) -> CircularLinkedNode[T]:
return self.tail.next
@head.setter
def head(self, node: CircularLinkedNode[T]):
self.tail.next = node
def appendleft(self, value: T) -> None:
if not self:
self.tail = CircularLinkedNode(value)
else:
self.head = CircularLinkedNode(value, self.head)
def reverse(self) -> None:
if not self:
return
node = self.head
last_node = self.tail
while node is not self.tail:
node.next, last_node, node = last_node, node, node.next
self.tail.next, self.tail = last_node, self.head
class CircularDoublyLinkedList(BaseCircularLinkedList[T], BaseDoublyLinkedList[T]):
tail: Optional[CircularDoublyLinkedNode[T]]
head: Optional[CircularDoublyLinkedNode[T]]
def __init__(self, values: Iterable[T] = ()) -> None:
values_iter = iter(values)
try:
head = CircularDoublyLinkedNode(next(values_iter))
except StopIteration:
head = None
node = head
for value in values_iter:
node.next = CircularDoublyLinkedNode(value, head, node)
node = node.next
head.last = node
self.tail = node
@property
def head(self) -> CircularDoublyLinkedNode[T]:
return self.tail.next
def __reversed__(self) -> Iterator[T]:
if not self:
return
yield self.tail.value
node = self.tail.last
while node is not self.tail:
yield node.value
node = node.last
def append(self, value: T) -> None:
if not self:
self.tail = CircularDoublyLinkedNode(value)
else:
self.tail = CircularDoublyLinkedNode(value, self.head, self.tail)
self.tail.last.next = self.tail
self.head.last = self.tail
def appendleft(self, value: T) -> None:
if not self:
self.tail = CircularDoublyLinkedNode(value)
else:
self.tail.next = CircularDoublyLinkedNode(value, self.head, self.tail)
self.head.next.last = self.tail.next
def pop(self) -> T:
if not self:
raise IndexError
value = self.tail.value
if self.tail is self.head:
self.tail = None
else:
self.tail.last.next, self.head.last, self.tail = self.head, self.tail.last, self.tail.last
return value
def popleft(self) -> T:
if not self:
raise IndexError
value = self.head.value
if self.tail is self.head:
self.tail = None
else:
self.tail.next = self.tail.next.next
self.tail.next.last = self.tail
return value
def reverse(self) -> None:
if not self:
return
node = self.head
while node is not self.tail:
node.next, node.last, node = node.last, node.next, node.next
self.tail.next, self.tail.last, self.tail = self.tail.last, self.tail.next, self.tail.next
"""Each ListNode holds a reference to its previous node
as well as its next node in the List."""
class ListNode:
def __init__(self, value, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
"""Wrap the given value in a ListNode and insert it
after this node. Note that this node could already
have a next node it is point to."""
def insert_after(self, value):
current_next = self.next
self.next = ListNode(value, self, current_next)
if current_next:
current_next.prev = self.next
"""Wrap the given value in a ListNode and insert it
before this node. Note that this node could already
have a previous node it is point to."""
def insert_before(self, value):
current_prev = self.prev
self.prev = ListNode(value, current_prev, self)
if current_prev:
current_prev.next = self.prev
"""Rearranges this ListNode's previous and next pointers
accordingly, effectively deleting this ListNode."""
def delete(self):
if self.prev:
self.prev.next = self.next
if self.next:
self.next.prev = self.prev
"""Our doubly-linked list class. It holds references to
the list's head and tail nodes."""
class DoublyLinkedList:
def __init__(self, node=None):
self.head = node
self.tail = node
self.length = 1 if node is not None else 0
def __len__(self):
return self.length
def add_to_head(self, value):
pass
def remove_from_head(self):
pass
def add_to_tail(self, value):
pass
def remove_from_tail(self):
pass
def move_to_front(self, node):
pass
def move_to_end(self, node):
pass
def delete(self, node):
pass
def get_max(self):
pass
import unittest
from doubly_linked_list import ListNode
from doubly_linked_list import DoublyLinkedList
class DoublyLinkedListTests(unittest.TestCase):
def setUp(self):
self.node = ListNode(1)
self.dll = DoublyLinkedList(self.node)
def test_list_remove_from_tail(self):
self.dll.remove_from_tail()
self.assertIsNone(self.dll.head)
self.assertIsNone(self.dll.tail)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_tail(33)
self.assertEqual(self.dll.head.value, 33)
self.assertEqual(self.dll.tail.value, 33)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_tail(), 33)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_tail(68)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_tail(), 68)
self.assertEqual(len(self.dll), 0)
def test_list_remove_from_head(self):
self.dll.remove_from_head()
self.assertIsNone(self.dll.head)
self.assertIsNone(self.dll.tail)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_head(2)
self.assertEqual(self.dll.head.value, 2)
self.assertEqual(self.dll.tail.value, 2)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_head(), 2)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_head(55)
self.assertEqual(len(self.dll), 1)
self.assertEqual(self.dll.remove_from_head(), 55)
self.assertEqual(len(self.dll), 0)
def test_list_add_to_tail(self):
self.assertEqual(self.dll.tail.value, 1)
self.assertEqual(len(self.dll), 1)
self.dll.add_to_tail(30)
self.assertEqual(self.dll.tail.prev.value, 1)
self.assertEqual(self.dll.tail.value, 30)
self.assertEqual(len(self.dll), 2)
self.dll.add_to_tail(20)
self.assertEqual(self.dll.tail.prev.value, 30)
self.assertEqual(self.dll.tail.value, 20)
self.assertEqual(len(self.dll), 3)
def test_node_delete(self):
node_1 = ListNode(3)
node_2 = ListNode(4)
node_3 = ListNode(5)
node_1.next = node_2
node_2.next = node_3
node_2.prev = node_1
node_3.prev = node_2
node_2.delete()
self.assertEqual(node_1.next, node_3)
self.assertEqual(node_3.prev, node_1)
def test_node_insert_before(self):
self.node.insert_before(0)
self.assertEqual(self.node.prev.value, 0)
def test_list_add_to_head(self):
self.assertEqual(self.dll.head.value, 1)
self.dll.add_to_head(10)
self.assertEqual(self.dll.head.value, 10)
self.assertEqual(self.dll.head.next.value, 1)
self.assertEqual(len(self.dll), 2)
def test_node_insert_after(self):
self.node.insert_after(2)
self.assertEqual(self.node.next.value, 2)
def test_list_move_to_end(self):
self.dll.add_to_head(40)
self.assertEqual(self.dll.tail.value, 1)
self.assertEqual(self.dll.head.value, 40)
self.dll.move_to_end(self.dll.head)
self.assertEqual(self.dll.tail.value, 40)
self.assertEqual(self.dll.tail.prev.value, 1)
self.assertEqual(len(self.dll), 2)
self.dll.add_to_tail(4)
self.dll.move_to_end(self.dll.head.next)
self.assertEqual(self.dll.tail.value, 40)
self.assertEqual(self.dll.tail.prev.value, 4)
self.assertEqual(len(self.dll), 3)
def test_list_move_to_front(self):
self.dll.add_to_tail(3)
self.assertEqual(self.dll.head.value, 1)
self.assertEqual(self.dll.tail.value, 3)
self.dll.move_to_front(self.dll.tail)
self.assertEqual(self.dll.head.value, 3)
self.assertEqual(self.dll.head.next.value, 1)
self.assertEqual(len(self.dll), 2)
self.dll.add_to_head(29)
self.dll.move_to_front(self.dll.head.next)
self.assertEqual(self.dll.head.value, 3)
self.assertEqual(self.dll.head.next.value, 29)
self.assertEqual(len(self.dll), 3)
def test_list_delete(self):
self.dll.delete(self.node)
self.assertIsNone(self.dll.head)
self.assertIsNone(self.dll.tail)
self.assertEqual(len(self.dll), 0)
self.dll.add_to_tail(1)
self.dll.add_to_head(9)
self.dll.add_to_tail(6)
self.dll.delete(self.dll.head)
self.assertEqual(self.dll.head.value, 1)
self.assertEqual(self.dll.tail.value, 6)
self.assertEqual(len(self.dll), 2)
self.dll.delete(self.dll.head)
self.assertEqual(self.dll.head.value, 6)
self.assertEqual(self.dll.tail.value, 6)
self.assertEqual(len(self.dll), 1)
def test_get_max(self):
self.assertEqual(self.dll.get_max(), 1)
self.dll.add_to_tail(100)
self.assertEqual(self.dll.get_max(), 100)
self.dll.add_to_tail(55)
self.assertEqual(self.dll.get_max(), 100)
self.dll.add_to_tail(101)
self.assertEqual(self.dll.get_max(), 101)
if __name__ == '__main__':
unittest.main()For more background on the different types of data structures in Python, check out the following articles:
A Linked List is a linear data structure. They are a sequence of data, connected together by links or pointers.
Linked Lists are a chain of nodes, connected together by links. Every node (fundamental block of a linked list) contains the following fields:
Data -> The item to be stored in the node.
Next -> The link or reference to the next node.
In a linked list, the first node is called the head and the last node is determined by the condition that the next points to a null value.
Due to their dynamic size allocation and ease of insertion/deletion, linked lists are applied in a lot of use cases.
They’re used to implement a lot of complex data structures like the adjacency list in graphs.
They are used for lifecycle management in operating systems.
There are two main types of Linked Lists:
Singly Linked Lists
Doubly Linked Lists
In the following example, we’ll implement a singly linked list from scratch in Python. This contains the following methods:
ll.search(head, data) -> Search the given element in the Linked List.
ll.print_list() -> Print the linked list.
ll.size() -> Return the length of the linked list.
A doubly linked list is similar to a singly linked list. It differs in that it also contains a link to the previous node.
We implement the following methods for the Doubly Linked List data structure:
dll.addNodeLast(x) -> Adds a node at the right end of the linked list.
dll.insertNode(pos, x) -> Adds a node at the position specified.
dll.removeNode(x) -> Removes the specified node.
First, try implementing the Linked Lists as shown above, and then try running them. Once you’ve mastered the implementation, try the given problem-sets to master linked lists.
Merge Two Sorted Lists -
Remove nth Node from the End of the List -
Rotate List -
Palindrome Linked List -
In single linked list each node of the list has two components, the actual value of the node and the reference to the next node in the linked list. In the doubly linked list, each node has three components: the value of the node, the reference to the previous node, and the reference to the next node. For the start node of the doubly linked list, the reference to the previous node is null. Similarly, for the last node in the doubly linked list, the reference to next node is null.
Following are some of the pros and cons of a doubly linked list:
Pros
Unlike a single linked list, the doubly linked list can be traversed and searched in both directions. The reference to the next node helps in traversing the node in the forward direction while the references to the previous nodes allow traversal in the backward direction.
Basic operations such as insertion and deletion are easier to implement in the doubly linked lists since, unlike single linked lists, we do not need to traverse to the predecessor node and store its reference. Rather, in a doubly linked list the reference of the predecessor node can be retrieved from the node that we want to delete.
Cons
One of the major drawbacks of the doubly linked list is that you need more memory space to store one extra reference for each node.
A few additional steps are required to be performed in order to perform insertion and deletion operations.
In this section, we will see how we can create a very simple doubly linked list in Python. If you have read and of this series of articles, the code should be pretty straight-forward.
As always, let's first create a class for the single node in the list. Add the following code to your file:
You can see in the above code, we create a Node class with three member variables: item, nref, and pref. The item variable will store the actual data for the node. The nref stores the reference to the next node, while pref stores the reference to the previous node in the doubly linked list.
Next, we need to create the DoublyLinkedList class, which contains different doubly linked list related functions. Add the following code:
Throughout this article we will keep adding functions to this class.
Inserting Items in Doubly Linked List
In this section, we will see the different ways of inserting items in a doubly linked list.
Inserting Items in Empty List
The easiest way to insert an item in a doubly linked list is to insert an item in the empty list. The following script inserts an element at the start of the doubly linked list:
In the script above, we define a method insert_in_emptylist(). The method first checks whether the self.start_node variable is None or not. If the variable is None, it means that the list is actually empty. Next, a new node is created and its value is initialized by the value passed as a parameter to the data parameter of the insert_in_emptylist() function. Finally, the value of self.start_node variable is set to the new node. In case if the list is not empty, a message is simply displayed to the user that the list is not empty.
Add the insert_in_emptylist() method to the DoublyLinkedList class that you created earlier.
Inserting Items at the Start
To insert an item at the beginning of the doubly linked list, we have to first check whether the list is empty or not. If the list is empty, we can simply use the logic defined in the insert_in_emptylist() to insert the element since in an empty list, the first element is always at the start.
Else, if the list is not empty, we need to perform three operations:
For the new node, the reference to the next node will be set to self.start_node.
For the self.start_node the reference to the previous node will be set to the newly inserted node.
Finally, the self.start_node will become the newly inserted node.
The following script inserts an item at the start of the doubly linked list:
Add the insert_at_start() method to the DoublyLinkedList class that you created earlier.
Inserting Items at the End
Inserting an element at the end of the doubly linked list is somewhat similar to inserting an element at the start. At first, we need to check if the list is empty. If the list is empty then we can simply use the insert_in_emptylist() method to insert the element. If the list already contains some element, we traverse through the list until the reference to the next node becomes None. When the next node reference becomes None it means that the current node is the last node.
The previous reference for the new node is set to the last node, and the next reference for the last node is set to the newly inserted node. The script for inserting an item at the last node is as follows:
Add the insert_at_end() method to the DoublyLinkedList class that you created earlier.
Inserting Item after another Item
To insert an item after another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".
Otherwise we iterate through all the nodes in the doubly linked list. In case if the node after which we want to insert the new node is not found, we display the message to the user that the item is not found. Else if the node is found, it is selected and we perform four operations:
Set the previous reference of the newly inserted node to the selected node.
Set the next reference of the newly inserted node to the next reference of the selected.
If the selected node is not the last node, set the previous reference of the next node after the selected node to the newly added node.
Finally, set the next reference of the selected node to the newly inserted node.
The script for inserting item after another item is as follows:
Add the insert_after_item() method to the DoublyLinkedList class that you created earlier.
Inserting Item before another Item
To insert an item before another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".
Otherwise we iterate through all the nodes in the doubly linked list. In case if the node before which we want to insert the new node is not found, we display the message to the user that the item is not found. Else if the node is found, it is selected and we perform four operations:
Set the next reference of the newly inserted node to the selected node.
Set the previous reference of the newly inserted node to the previous reference of the selected.
Set the next reference of the node previous to the selected node, to the newly added node.
Finally, set the previous reference of the selected node to the newly inserted node.
The script for adding item before another item in a doubly linked list is as follows:
Add the insert_before_item() method to the DoublyLinkedList class that you created earlier.
Traversing a Doubly Linked List
Traversing a doubly linked list is very similar to traversing a single linked list. The script is as follows:
Add the traverse_list() method to the DoublyLinkedList class that you created earlier.
Deleting Elements from Doubly Linked List
Like insertion, there can be multiple ways to delete elements from a doubly linked list. In this section, we will review some of them.
Deleting Elements from the Start
The easiest way to delete an element from a doubly linked list is from the start. To do so, all you have to do is set the value of the start node to the next node and then set the previous reference of the start node to None. However before we do that we need to perform two checks. First, we need to see if the list is empty. And then we have to see if the list contains only one element or not. If the list contains only one element then we can simply set the start node to None. The following script can be used to delete elements from the start of the doubly linked list.
Add the delete_at_start() method to the DoublyLinkedList class that you created earlier.
Deleting Elements from the End
To delete the element from the end, we again check if the list is empty or if the list contains a single element. If the list contains a single element, all we have to do is to set the start node to None. If the list has more than one element, we iterate through the list until the last node is reached. Once we reach the last node, we set the next reference of the node previous to the last node, to None which actually removes the last node. The following script can be used to delete the element from the end.
Add the delete_at_end() method to the DoublyLinkedList class that you created earlier.
Deleting Elements by Value
Deleting an element by value is the trickiest of all the deletion functions in doubly linked lists since several cases have to be handled in order to remove an element by value. Let's first see how the function looks like and then we will see the explanation of the individual piece of code.
In the above script we create delete_element_by_value() function that takes the node value as parameter and deletes that node. At the beginining of the function we check if the list is empty or not. If the list is empty we simply display the user that the list is empty.
This logic is implemented in the following piece of code:
Next, we check if the list has a single element and that element is actually the element we want to delete. If the only element is the one that we want to delete, we simply set the self.start_node to None which means that the list will now have no item. If there is only one item and that is not the item that we want to delete, we will simply display the message that item to be deleted is not found.
The following piece of code implements this logic:
Next, we handle the case where the list has more than one items but the item to be deleted is the first item. In that case we simply execute the logic that we wrote for the method delete_at_start(). The following piece of code deletes an element from the start in case of multiple items:
Finally, if the list contains multiple items and the item to be deleted is not the first item, we traverse all the elements in the list except the last one and see if any of the nodes has the value that matches the value be deleted. If the node is found, we perform the following two operations:
Set the value of the next reference of the previous node to the next reference of the node to be deleted.
Set the previous value of the next node to the previous reference of the node to be deleted.
Finally, if the node to be deleted is the last node, the next reference of the node previous to the last node is set to None. The following script implements this logic:
Add the delete_element_by_value() method to the DoublyLinkedList class that you created earlier.
Reversing a Doubly Linked List
To reverse a doubly linked list, you basically have to perform the following operations:
The next reference of the start node should be set none because the first node will become the last node in the reversed list.
The previous reference of the last node should be set to None since the last node will become the previous node.
The next references of the nodes (except the first and last node) in the original list should be swapped with the previous references.
The script for reversing a doubly linked list is as follows:
Add the reverse_linked_list() method to the DoublyLinkedList class that you created earlier.
Testing Doubly Linked List Functions
In this section, we will test the doubly linked functions that we created in the previous sections.
Let's first create the object of the DoublyLinkedList class. Execute the following script:
Testing Insertion Functions
Let's test the insertion functions first. We'll first add elements in the empty list. Execute the following script:
Now if you traverse the list, you should see 50 as the only element in the list as shown below:
Output:
Now let's add a few elements at the start. Execute the following script:
Now if you traverse the list, you should see the following elements in the list:
To add the elements at the end, execute the following script:
Now if you traverse the doubly linked list, you should see the following elements:
Let's insert an element after 50.
Now the list should look like this:
Finally, let's add an element before item 29.
The list at this point of time, should contain the following elements:
Testing Deletion Functions
Let's now test the deletion functions on the items that we inserted in the last sections. Let's first delete an element from the start.
Item 18 will be removed and the list will now look like this:
Similarly, the following script deletes the element from the end of the doubly linked list:
Traversing the list now will return the following items:
Finally, you can also delete the elements by value using the delete_element_by_value() function as shown below:
If you traverse the list now, you will see that item 65 will be deleted from the list.
Testing Reverse Function
Finally, let's reverse the list using the reverse_linked_list() function. Execute the following script:
Now if you traverse the list, you will see the reversed linked list:
The doubly linked list is extremely useful specifically when you have to perform lots of inserts and delete operations. The links to the previous and next nodes make it very easy to insert and delete new elements without keeping track of the previous and next nodes.
In this article, we saw how doubly linked list can be implemented with Python. We also saw different ways to perform insert and delete operations on doubly linked list. Finally we studied how to reverse a doubly linked list.
The List is the same as arrays irrespective it can store different data types in it. We can access the list by using the start and end range which can be altered by using custom step function as the third argument.
Let’s define a variable named myList and declare a list of numbers from 1 to 9 in it.
List Slicing means accessing the particular element by index or slice or cut a particular range of elements from the .
Read =>
Source Code
Output
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
"""
You are given two non-empty linked lists representing
two non-negative integers. The digits are stored in reverse order
and each of their nodes contain a single digit.
Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero,
except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
"""
import unittest
#Syntax : list[ start : end : step ]myList = [1, 2, 3, 4, 5, 6, 7, 8, 9]
#index 0 1 2 3 4 5 6 7 8
# -9 -8 -7 -6 -5 -4 -3 -2 -1class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoubleLinkedList:
def __init__(self):
self.length = 0
self.head = None
self.tail = None
def prependNode(self, data):
newNode = Node(data)
if self.length == 0:
self.head = newNode
self.tail = newNode
newNode.next = newNode
newNode.prev = newNode
else:
newNode.next = self.head
newNode.prev = self.head.prev
self.head.prev.next = newNode
self.head.next.prev = newNode
self.head = newNode
self.length += 1
def appendNode(self, data):
newNode = Node(data)
if self.length == 0:
self.head = newNode
self.tail = newNode
newNode.next = newNode
newNode.prev = newNode
else:
curNode = self.head
while curNode.next != self.head:
curNode = curNode.next
newNode.next = self.head
newNode.prev = curNode
curNode.next = newNode
self.tail = newNode
self.length += 1
def printList(self):
# BUG: Only printing last Node
if self.length == 0:
return False
curNode = self.head
while curNode.next != self.head:
print(curNode.data)
curNode = curNode.next
dLL = DoubleLinkedList()
dLL.prependNode(1)
dLL.prependNode(2)
dLL.prependNode(3)
dLL.prependNode(4)
dLL.printList()
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SingleLinkedList:
def __init__(self):
self.length = 0
self.head = None
def prependNode(self, data):
newNode = Node(data)
newNode.next = self.head
self.head = newNode
self.length += 1
def appendNode(self, data):
newNode = Node(data)
if self.length == 0:
self.head = newNode
self.length += 1
return
else:
curNode = self.head
while curNode.next != None:
curNode = curNode.next
curNode.next = newNode
self.length += 1
def deleteNode(self, data):
if self.length == 0:
return false
curNode = self.head
if curNode.data == data:
self.head = self.head.next
curNode = None
return True
curNode = self.head
while curNode.next != None:
if curNode.next.data == data:
deleteNode = curNode.next
curNode.next = curNode.next.next
deleteNode.next = None
self.length -= 1
return True
else:
curNode = curNode.next
return False
def deleteAllNodes(self, data):
if(self.length == 0):
return
curNode = self.head
while self.head.data == data:
self.head = self.head.next
curNode.next = null
curNode = self.head
self.length -= 1
if curNode == None:
return
while curNode.next != None:
if curNode.next.data == data:
deleteNode = curNode.next
curNode.next = curNode.next.next
deleteNode.next = None
self.length -= 1
else:
curNode = curNode.next
return deleted
def isEmpty(self):
return True if self.length == 0 else False
def findNode(self, data):
curNode = self.head
while curNode.data != data:
if curNode.next == None:
return False
else:
curNode = curNode.next
return curNode
def getNextNode(self, node):
if(isinstance(node, Node)):
return node.next;
return False
def printList(self):
curNode = self.head
while curNode != None:
print(curNode.data)
curNode = curNode.next
sLL = SingleLinkedList()
# sLL.appendNode(1)
# sLL.appendNode(2)
# sLL.prependNode(3)
# sLL.appendNode(4)
# sLL.deleteNode(2)
#
# sLL.printList()
# print('List Length: {}'.format(sLL.length))
# print([ m for m in dir(sLL) if not m.startswith('__')])
class Node:
def __init__(self, data):
self.item = data
self.nref = None
self.pref = Noneclass DoublyLinkedList:
def __init__(self):
self.start_node = None def insert_in_emptylist(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
else:
print("list is not empty") def insert_at_start(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
print("node inserted")
return
new_node = Node(data)
new_node.nref = self.start_node
self.start_node.pref = new_node
self.start_node = new_node def insert_at_end(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
return
n = self.start_node
while n.nref is not None:
n = n.nref
new_node = Node(data)
n.nref = new_node
new_node.pref = n def insert_after_item(self, x, data):
if self.start_node is None:
print("List is empty")
return
else:
n = self.start_node
while n is not None:
if n.item == x:
break
n = n.nref
if n is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.pref = n
new_node.nref = n.nref
if n.nref is not None:
n.nref.prev = new_node
n.nref = new_node def insert_before_item(self, x, data):
if self.start_node is None:
print("List is empty")
return
else:
n = self.start_node
while n is not None:
if n.item == x:
break
n = n.nref
if n is None:
print("item not in the list")
else:
new_node = Node(data)
new_node.nref = n
new_node.pref = n.pref
if n.pref is not None:
n.pref.nref = new_node
n.pref = new_node def traverse_list(self):
if self.start_node is None:
print("List has no element")
return
else:
n = self.start_node
while n is not None:
print(n.item , " ")
n = n.nref def delete_at_start(self):
if self.start_node is None:
print("The list has no element to delete")
return
if self.start_node.nref is None:
self.start_node = None
return
self.start_node = self.start_node.nref
self.start_prev = None; def delete_at_end(self):
if self.start_node is None:
print("The list has no element to delete")
return
if self.start_node.nref is None:
self.start_node = None
return
n = self.start_node
while n.nref is not None:
n = n.nref
n.pref.nref = None def delete_element_by_value(self, x):
if self.start_node is None:
print("The list has no element to delete")
return
if self.start_node.nref is None:
if self.start_node.item == x:
self.start_node = None
else:
print("Item not found")
return
if self.start_node.item == x:
self.start_node = self.start_node.nref
self.start_node.pref = None
return
n = self.start_node
while n.nref is not None:
if n.item == x:
break;
n = n.nref
if n.nref is not None:
n.pref.nref = n.nref
n.nref.pref = n.pref
else:
if n.item == x:
n.pref.nref = None
else:
print("Element not found") if self.start_node is None:
print("The list has no element to delete")
return if self.start_node.nref is None:
if self.start_node.item == x:
self.start_node = None
else:
print("Item not found")
return if self.start_node.item == x:
self.start_node = self.start_node.nref
self.start_node.pref = None
return n = self.start_node
while n.nref is not None:
if n.item == x:
break;
n = n.nref
if n.nref is not None:
n.pref.nref = n.nref
n.nref.pref = n.pref
else:
if n.item == x:
n.pref.nref = None
else:
print("Element not found") def reverse_linked_list(self):
if self.start_node is None:
print("The list has no element to delete")
return
p = self.start_node
q = p.nref
p.nref = None
p.pref = q
while q is not None:
q.pref = q.nref
q.nref = p
p = q
q = q.pref
self.start_node = pnew_linked_list = DoublyLinkedList()new_linked_list.insert_in_emptylist(50)new_linked_list.traverse_list()50new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)18
5
10
50new_linked_list.insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)18
5
10
50
29
39
49 new_linked_list.insert_after_item(50, 65)18
5
10
50
65
29
39
49 new_linked_list.insert_before_item(29, 100)18
5
10
50
65
100
29
39
49 new_linked_list.delete_at_start()5
10
50
65
100
29
39
49 new_linked_list.delete_at_end()5
10
50
65
100
29
39new_linked_list.delete_element_by_value(65)new_linked_list.reverse_linked_list()39
29
100
50
10
5 # Each ListNode holds a reference to its previous node
# as well as its next node in the List.
class ListNode:
def __init__(self, value, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
def __repr__(self):
return (
"Value: {}, ".format(self.value if self.value else None)
+ "Prev: {}, ".format(self.prev.value if self.prev else None)
+ "Next: {} \n".format(self.next.value if self.next else None)
)
# Wrap the given value in a ListNode and insert it
# after this node. Note that this node could already
# have a next node it is pointing to.
def insert_after(self, value):
current_next = self.next
self.next = ListNode(value, self, current_next)
if current_next:
current_next.prev = self.next
# Wrap the given value in a ListNode and insert it
# before this node. Note that this node could already
# have a previous node it is pointing to.
def insert_before(self, value):
current_prev = self.prev
self.prev = ListNode(value, current_prev, self)
if current_prev:
current_prev.next = self.prev
# Rearranges this ListNode's previous and next pointers
# accordingly, effectively deleting this ListNode.
def delete(self):
if self.prev:
self.prev.next = self.next
if self.next:
self.next.prev = self.prev
# Our doubly-linked list class. It holds references to
# the list's head and tail nodes.
class DoublyLinkedList:
def __init__(self, node=None):
self.head = node
self.tail = node
self.length = 1 if node is not None else 0
def __repr__(self):
return f"Head: {self.head} \n Tail: {self.tail} \n Length: {self.length}"
def __len__(self):
return self.length
# Replaces the head of the list with a new value that is passed in.
def add_to_head(self, value):
new_node = ListNode(value)
self.length += 1
# if there is no head or tail, it needs to become both:
if not self.head and not self.tail:
self.head = new_node
self.tail = new_node
# otherwise it only needs to become the head:
else:
self.head.prev = new_node
new_node.next = self.head
self.head = new_node
# Replaces the tail of the list with a new value that is passed in.
def remove_from_head(self):
# if there is no head, just return None because we can't remove
if not self.head:
return None
# reduce the length
self.length -= 1
# we need to store the current head to return it once removed
current_head = self.head
# if there is solely one node, we set both head and tail to None
if self.head == self.tail:
self.head = None
self.tail = None
return current_head.value
# changes the head to the next node
else:
self.head = self.head.next
# Removes pointers to any previous node
self.head.prev = None
return current_head.value
# Removes the head node and returns the value stored in it.
def add_to_tail(self, value):
new_node = ListNode(value)
self.length += 1
# if there is no head or tail, it needs to become both:
if not self.head and not self.tail:
self.head = new_node
self.tail = new_node
# otherwise it only needs to become the tail:
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
# Removes the tail node and returns the value stored in it
def remove_from_tail(self):
# if there is no tail, just return None because we can't remove
if not self.tail:
return None
# reduce the length
self.length -= 1
# we need to store the current tail to return it once removed
current_tail = self.tail
# if there is solely one node, we set both head and tail to None
if self.head == self.tail:
self.head = None
self.tail = None
return current_tail.value
# changes the tail to the next node
else:
self.tail = self.tail.prev
# Removes pointers to any next node
self.tail.next = None
return current_tail.value
# Takes a reference to a node in the list and moves it to the front of the list, shifting all other list nodes down.
def move_to_head(self, node):
# if the passed node is already the head, we just return it
if node is self.head:
return node
# if the passed node is the tail, we need to remove it from the tail
if node is self.tail:
self.remove_from_tail()
else:
node.delete()
self.length -= 1
# we should add it but only the value of the passed node
self.add_to_head(node.value)
# Takes a reference to a node in the list and moves it to the end of the list, shifting all other list nodes up.
def move_to_tail(self, node):
if node is self.tail:
return node
if node is self.head:
self.remove_from_head()
else:
node.delete()
self.length -= 1
self.add_to_tail(node.value)
# Takes a reference to a node in the list and removes it from the list. The deleted node's `previous` and `next` pointers should point to each afterwards.
def delete(self, node):
if self.head is self.tail:
self.remove_from_head()
elif node is self.head:
self.remove_from_head()
elif node is self.tail:
self.remove_from_tail()
else:
node.delete()
return node.value
# Returns the maximum value in the list.
def get_max(self):
# if there is no head, we know the list is empty
if not self.head:
return None
# we'll set our starting max value as the first value we'll begin looping through in the list, the head
max_value = self.head.value
# we'll set a current value to check against
current = self.head
while current:
if current.value > max_value:
max_value = current.value
# increment current
current = current.next
# once all values are checked, return max value
return max_value
ll = DoublyLinkedList()
print(f"ll: {ll}") # should be empty
ll.add_to_head(2) # should be 2
ll.add_to_head(5) # should be 5,2
ll.add_to_head(7) # should be 7,5,2
ll.remove_from_head() # should be 5,2
ll.add_to_tail(9) # should be 5,2,9
ll.add_to_tail(11) # should be 5,2,9,11
ll.add_to_tail(13) # should be 5,2,9,11,13
ll.remove_from_tail() # should be 5,2,9,11
ll.get_max() # should return 11
print(f"ll: {ll}") # return length 4, head: 5, tail: 11
Blockchain, a complex data structure that is used for cryptocurrencies and ledgers use a linked list at their core.
ll.insert(ele) -> Insert the given node into the linked list.
ll.delete(data) -> Delete the given element from the linked list.
dll.showReverse() -> Prints the linked list in reverse.
dll.show() -> Prints the linked list.
Construct a Doubly Linked List from 2D Matrix - GeeksforGeeks
Reverse a Doubly Linked List - GeeksforGeeks
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
# Class to create a Linked List
class LinkedList(object):
def __init__(self, head=None):
self.head = head
# Search an element and print its index
def search(self, head, data, index):
if head.data == data:
print (index)
else:
# Make recursive calls
if head.next:
return self.search(head.next, data, index+1)
else:
raise ValueError("Node not in linked list")
# Print the linked list
def print_list(self):
if self.head == None:
raise ValueError("List is empty")
current = self.head
while(current):
print (current.data, end=" ")
current = current.next
print ('\n')
# Find length of Linked List
def size(self):
if self.head == None:
return 0
size = 0
current = self.head
while(current):
size += 1
current = current.next
return size
# Insert a node in a linked list
def insert(self, data):
node = Node(data)
if not self.head:
self.head = node
else:
node.next = self.head
self.head = node
# Delete a node in a linked list
def delete(self, data):
if not self.head:
return
temp = self.head
# Check if head node is to be deleted
if head.data == data:
head = temp.next
print ("Deleted node is " + str(head.data))
return
while(temp.next):
if (temp.next.data == data):
print ("Node deleted is " + str(temp.next.data))
temp.next = temp.next.next
return
temp = temp.next
print ("Node not found")
returnclass Node:
def __init__(self, val):
self.value = val
self.next = None
self.prev = None
class DoublyList:
def __init__(self, val):
self.head = Node(val)
self.tail = self.head
def addNodeLast(self, val):
current = self.head
while current.next != None:
current = current.next
newNode = Node(val)
current.next = newNode
newNode.prev = current
self.tail = newNode
def insertNode(self, val, newVal):
if self.tail.value == val:
self.addNodeLast(newVal)
elif self.head.value == val:
newNode = Node(newVal)
newNode.next = self.head.next
newNode.prev = self.head
newNode.next.prev = newNode
self.head.next = newNode
else:
current = self.head.next
while current.value != val:
current = current.next
newNode = Node(newVal)
newNode.next = current.next
newNode.next.prev = newNode
newNode.prev = current
current.next = newNode
def removeNode(self, val):
if self.head.value == val:
self.head = self.head.next
self.head.prev = None
elif self.tail.value == val:
self.tail = self.tail.prev
self.tail.next = None
else:
current = self.head.next
while current.value != val:
current = current.next
current.prev.next = current.next
current.next.prev = current.prev
def showReverse(self):
current = self.tail
while current != None:
print(current.value)
current = current.prev
def show(self):
current = self.head
while current != None:
print(current.value)
current = current.nextprint('Original List:',myList)
print('First Element:',myList[0]) #Prints the first element of the list or 0th index of the list
print('Element at 3rd Index position:',myList[2]) #Prints the 3rd element of the list
print('Elements from 0th Index to 4th Index:',myList[0: 5]) #Prints elements of the list from 0th index to 4th index. IT DOESN'T INCLUDE THE LAST INDEX
print('Element at -7th Index:',myList[-7]) #Prints the -7th or 3rd element of the list#To append an element to a list
myList.append(10)
print('Append:',myList)#To find the index of a particular element
print('Index of element \'6\':',myList.index(6)) #returns index of element '6'#To sort the list
myList.sort()
print("myList : ",myList)#To pop last element
print('Poped Element:',myList.pop())#To remove a particular element from the list BY NAME
myList.remove(6)
print('After removing \'6\':',myList)#To insert an element at a specified Index
myList.insert(5, 6)
print('Inserting \'6\' at 5th index:',myList)#To count number of occurences of a element in the list
print('No of Occurences of \'1\':',myList.count(1))#To extend a list that is insert multiple elemets at once at the end of the list
myList.extend([11,0])
print('Extending list:',myList)#To reverse a list
myList.reverse()
print('Reversed list:',myList)#Syntax: list[start: end: step]
myList = [1, 2, 3, 4, 5, 6, 7, 8, 9]
#index 0 1 2 3 4 5 6 7 8
# -9 -8 -7 -6 -5 -4 -3 -2 -1
#List Slicing
print('Original List:',myList)
print('First Element:',myList[0]) #Prints the first element of the list or 0th element of the list
print('Element at 2nd Index position:',myList[2]) #Prints the 2nd element of the list
print('Elements from 0th Index to 4th Index:',myList[0: 5]) #Prints elements of the list from 0th index to 4th index. IT DOESN'T INCLUDE THE LAST INDEX
print('Element at -7th Index:',myList[-7]) #Prints the -7th or 3rd element of the list
#To append an element to a list
myList.append(10)
print('Append:',myList)
#To find the index of a particular element
print('Index of element \'6\':',myList.index(6)) #returns index of element '6'
#To sort the list
myList.sort()
#To pop last element
print('Poped Element:',myList.pop())
#To remove a particular element from the lsit BY NAME
myList.remove(6)
print('After removing \'6\':',myList)
#To insert an element at a specified Index
myList.insert(5, 6)
print('Inserting \'6\' at 5th index:',myList)
#To count number of occurences of a element in the list
print('No of Occurences of \'1\':',myList.count(1))
#To extend a list that is insert multiple elemets at once at the end of the list
myList.extend([11,0])
print('Extending list:',myList)
#To reverse a list
myList.reverse()
print('Reversed list:',myList)
