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.
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.
# 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 null
2. 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).
def __init__(lld): #Linked list creation
lld.start_node = None #Link to first node
3. 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.
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 one
4. 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
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 iteration
5. 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.
new_linked_listdemo = LinkedListdemo() # new object
new_linked_listdemo.insert_at_last("January") # inserting nodes at end
6. List Dataset
Using the same linked list creation object class, scan through the dataset and view it.
new_linked_listdemo.navigate_list() # traversing the list
7. Insert in The Beginning
Make the new node as the starting node and the existing starting node as the second node.
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 list
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.
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 link
9. Inserting Node After an Existing Node
new_linked_listdemo.navigate_list() # traverssing the list
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.
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 next
11. Test the Delete Function
new_linked_listdemo.navigate_list() # traverssing the list
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
This is a guide to Linked List in Python. Here we also discuss the definition and linked list operations along with examples. You may also have a look at the following articles to learn more –