Linked list is one of important data structure in software development and if you're from a different background other then CS then it would be quite tedious to master. Here I will present a simple way to represent the Linked list in Python.
So first What is Linked list?
Linked List a kind of
Data structure used in software development. In this data structure, data is represented in Nodes where every node contains a pair
(data,pointer) where data is from current node and pointer is pointing to next node.
Typically Linked list can represented as below.
Now To create a
linked list, first we had to create a typical Node which store all the information.
class Node(): def __init__(self,data=None, next_node=None): self.data= data self.next_node= next_node def get_data(self): return self.data def get_next_node(self): return self.next_node def set_next_node(self,new_node): self.next_node= new_node
Now Let's start with
class Linkedlist(): def __init__(self,head=None): self.head=head
Define a method to
add a new item to linked list. Addition of the data will done on the start of the linked list. So to add a new item, the new node pointer should point where the head node is pointing now (simple logic) and newly created node will became head now.
def add(self,data): new_node= Node(data) #create a new node new_node.set_next_node(self.head) self.head= new_node
Define a method to get the
size of the linked list. For this traverse the entire linked list, start from head node, update the count, visit the next node , until the final node.
def size(self): current_node = self.head count =0 while current_node: count = count + 1 current_node= current_node.get_next_node() return count
Now Let's write a function to
search the given data into a given linked list.For this we will use the same logic we used for size method. Start from the head , compare the node-data to the data(search-data), if not matched, then visit the next node, repeat the same. If the data is not in the linked list then raise a
def search(self,data): current_node = self.head found = False while current_node and found is False: if current_node.get_data() == data: found = True else: current_node = current_node.get_next_node() if current_node is None: raise ValueError("Data is not on Show") return current_node
Now Let's write a method to
delete some data in linked list. But before this, Let's first understand how deletion work in linked list.
To delete a node, Just remove the pointer pointing to the node(to be deleted). Here We will just update our search method.
def delete(self,data): current_node = self.head previous_node =None found= False while current_node and found is False: if current_node.get_data() == data: found= True else: previous_node= current_node current_node = current_node.get_next_node() if current_node is None: raise ValueError("Data is not on Show") if previous_node is None: self.head= current_node.get_next_node() else: previous_node.set_next_node(current_node.get_next_node())
Below method is used to print the content of linked list. [This is not a grate way]
def __str__( self ) : string = "" p = self.head if p != None : while p.get_next_node() != None : string += str(p.get_data()) p = p.get_next_node() string += str(p.get_data()) return string
Finally we know how to implement a linked list. Now Implement this and if there is something you need help let us know.Published On : 2017-01-30 Tweet