Linked List Data Structure in Python
Linked lists are dynamic data structures where nodes can be added, deleted or updated with a minimal cost. Also linked lists do not require access to a large contiguous block of memory at compile time, but rather accessing memory as needed during runtime. This flexibility makes linked lists attractive data structures for many practical applications.
Table of Contents
- Linked List: Introduction
- Uses of Linked Lists
- Implementing Linked Lists
- Conclusion
Linked List: Introduction
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 contemt is stored in a node.
- Next -> This indicates next node.
Uses of Linked Lists
Linked lists have many uses. For example, implementing data structures that appear to the end user to be mutable arrays.
If you are using a programming language that provides implementations of various collections, many of those collections will be implemented using linked lists. When programming in those languages, you won't often be implementing a linked list yourself but it might be wise to understand them so you can understand what tradeoffs the libraries you use are making. In other words, the set "just part of computer science theory" contains elements that you just need to know if you are going to write programs that just work.
Implementing Linked Lists
There are two main types of Linked Lists:
- Singly Linked Lists
-
Doubly Linked Lists
Singly 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.
ll.insert(ele) -> Insert the given node into the linked list.
ll.delete(data) -> Delete the given element from the linked list.
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")
return
Doubly Linked Lists
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.
- dll.showReverse() -> Prints the linked list in reverse.
- dll.show() -> Prints the linked list.
class 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.next
Circular Linked List
In circular linked list the last node of the list holds the address of the first node hence forming a circular chain.
We will learn about all the 3 types of linked list, one by one, in the next tutorials. So click on Next button, let's learn more about linked lists.
Conclusion
Linked list is a simple data structure which can be used to implement Stacks , Queues.Linked Lists can also be used to implement Graphs. (Adjacency list representation of Graph).Implementing Hash Tables :- Each Bucket of the hash table can itself be a linked list. (Open chain hashing) so understanding linked list can be very useful.
Top comments (0)