Updated April 11, 2023
Definition of Linked List in Python
Linked list in Python provides a logical connection between data elements that are stored in memory in different locations physically. Data elements are stored in nodes along with reference links to the next immediate data element. Logical sequencing of data is achieved in Python through these links in data nodes and the entire gamut of data can be accessed sequentially using these links by navigating from the first data element to the next and so on.
Linked list in Python removes the hassle of pre-defining the memory blocks, provides flexibility to scale up data dynamically, simplifies the data operations, and ensures optimum usage of memory.
Singly Linked List
Singly-linked list is the fundamental type among various types of linked lists that are available in python. Other types such as Doubly linked list, Circular linked list were built over the basics of singly linked list. Let’s focus more on singly linked list
Features of singly linked list are
- Header of dataset will always lead to first data element.
- Each node contains data and link to next data.
- The link in the last node is empty.
- This list is also known as one way chain because the data elements can be accessed in only direction i.e. first to last. Navigation through dataset in reverse direction is not possible.
- Any data element in this list cannot be accessed randomly and we will have to necessarily traverse sequentially from the first node one by one.
Pictorial representation
Linked List Operations with Examples
1. Node creation
A program class to create a node should be defined as a first step in the python program and the data objects can be created as when required.
Code:
# Linked list Concepts - Demo Program
class Node:
def __init__(data_node, data):
data_node.item = data #node is created with data
data_node.ref = None #Link is made null2. Linked List Creation
Another program class to create linked list with initial values should be defined in the program as next step. This class would contain steps for subsequent operations like Inserting, Delete, Traverse (Navigation).
Code:
class LinkedListdemo:
def __init__(lld): #Linked list creation
lld.start_node = None #Link to first node3. Initial Data Loading (Insert at The End)
Ideally the initial loading can happen from the end of the empty data set. While inserting a new data, If the dataset is empty make the new node as the first and last node and exit. If data is present in the dataset then navigate to end, make the current last node as last but one node. New node will be the last.
Code:
def insert_at_last(ial, data):
new_node = Node(data) # move data
if ial.start_node is None: # empty set
ial.start_node = new_node
return
n = ial.start_node
while n.ref is not None:
n= n.ref
n.ref = new_node; #new node is the last
#old last is last but one4. Navigating through data set
While navigating check whether the list is empty or not. Use the start node link to reach first node and use the link present in the first node to reach second and move on till the end
Code:
def navigate_list(nll):
if nll.start_node is None: # if there is no first node
print("List has no element") #it is empty list
return
else:
print ("DATA LINK to NEXT") # Header
print ("\n") # blank line
print (" ", nll.start_node) # Link to first node
n = nll.start_node # start from first
while n is not None:
print(n.item , n.ref) # Print Data and next link
n = n.ref # loop iteration5. Appending Nodes to Dataset
With all definitions are over, create a working object for linked list creation module and invoke it for inserting new nodes at the end.
Code:
new_linked_listdemo = LinkedListdemo() # new object
new_linked_listdemo.insert_at_last("January") # inserting nodes at end
new_linked_listdemo.insert_at_last("February")
new_linked_listdemo.insert_at_last("March")
new_linked_listdemo.insert_at_last("April")
new_linked_listdemo.insert_at_last("May")
new_linked_listdemo.insert_at_last("June")
new_linked_listdemo.insert_at_last("July")
new_linked_listdemo.insert_at_last("August")
new_linked_listdemo.insert_at_last("September")
new_linked_listdemo.insert_at_last("October")
new_linked_listdemo.insert_at_last("November")
new_linked_listdemo.insert_at_last("December")6. List Dataset
Using the same linked list creation object class, scan through the dataset and view it.
Code:
new_linked_listdemo.navigate_list() # traversing the listOutput:
7. Insert in The Beginning
Make the new node as the starting node and the existing starting node as the second node. Code:
def insert_at_beginning(iab, data):
new_node = Node(data) # move data
new_node.ref = iab.start_node # Current first as second
iab.start_node= new_node # new as latest first
new_linked_listdemo.insert_at_beginning("Pre-January")
new_linked_listdemo.navigate_list() # traverssing the listOutput:
8. Insert Next to An Existing Item
Reach the existing item, make it as previous node for the new node. Make the new node as previous node to the next node.
Code:
def insert_nextto_item(inti, x, data):
n = inti.start_node
while n is not None:
if n.item == x: # match the item
break
n = n.ref
if n is None: # no match
print("item not in the list")
else:
new_node = Node(data)
new_node.ref = n.ref # Swap new node address and previous
n.ref = new_node # node link9. Inserting Node After an Existing Node
new_linked_listdemo.insert_nextto_item("March","Post-march")
new_linked_listdemo.navigate_list() # traverssing the listOutput:
10. Deletion of Nodes
First Node – Make the second node as the starting node Last Node – Reach the last but one node and blank out the next link Any Middle node identified by content – Reach that node and change the link of the previous node to point to next node with reference to node to be deleted.
Code:
def delete_at_beginning(dab):
if dab.start_node is None: # Empty list
print("Empty List")
return
dab.start_node = dab.start_node.ref # make second node as initial
def delete_at_last(dal):
if dal.start_node is None:
print("Empty list")
return
n = dal.start_node
while n.ref.ref is not None: # Search last but one node
n = n.ref
n.ref = None # blank out the link
def delete_element_by_content(debc, x):
n = debc.start_node
while n.ref is not None:
if n.ref.item == x: # match found
break
n = n.ref
if n.ref is None:
print("no such item")
else:
n.ref = n.ref.ref # change previous node link with next11. Test the Delete Function
Code:
new_linked_listdemo.delete_at_beginning()
new_linked_listdemo.delete_at_last()
new_linked_listdemo.delete_element_by_content("August")
new_linked_listdemo.navigate_list() # traverssing the listOutput:
12. Doubly Linked List
Features of this list are
- Each data node has actual data and two links viz., Previous link to connect to previous node and next link to connect to next node as in singly linked list.
- For the first node previous link will be null and for the last node next link will be null.
- Navigation is possible in forward direction as well as reverse direction. Data can be read first to last and last to first. But random access only is not possible.
13. Circular Singly Linked List
Difference between singly linked list and circular singly linked list is
- The link in the last node is always updated with the memory address of the first node
- It becomes circular and traversing through the data elements becomes simpler
- Strictly speaking there is no first node or last node in this list
14. Circular Doubly Linked List
Difference between doubly linked list and circular doubly linked list is
- The next link in the last node is always updated with the memory address of the first node.
- The previous link in the first node is always updated with memory address of the last node
- Data can be accessed sequentially from any place to any other place in any direction
Recommended Articles
We hope that this EDUCBA information on “Linked List in Python” was beneficial to you. You can view EDUCBA’s recommended articles for more information.
