We will be implementing a Linked List data structure using python and we will be implementing methods to add, delete, search, and a way to get the size of the entire list for us. In our previous article, I explained what a Linked List was and why it’s important to use one.

Python is a language that’s very easy to read and will allow us to implement a list without too many details necessary to get started.

Creating the structure

We will need to create a node structure first to begin the linking of our chain. Note that we can use any data type in this node as we’d like and we can even create multiple Node structures with different data types.

Class Node:
	def __init__(self, data=None):
		Self.next = None
		Self.data = data

What we did here is to create a reference to the next node in the list, even if at this moment it’s only pointing to nothing. When we add more nodes to the list, we will set self.next to point to the next node in the list. Our data could be anything, when we initialize our object that’s when we’ll add the data value as an argument.

Example:

Node(“Happy Days”)

Node(45)

Node(3.45)

We need to create a list structure now and set it initially to empty. The self.end will represent the first node in the list.

Class LinkedList:
	def __init__(self):
		self.end= None

With the setup of the list out of the way, let’s implement a way to add to the list efficiently.

Keeping Track of the Size of the List

I probably should’ve added this to the initial setup of our linked list in the beginning, but this should be easy to implement if you think about it. All we would have to do is create a self.count variable in our def __init__() class.

Then whenever we append or delete we increment or decrement the values as the operation occurs.

class LinkedList:
    def __init__(self, data=None):
        #... setup from before and add the bottom counter variable
        self.count = 0 #initialize a counter variable

Inserting into the List

In order to add to the list, we would have to traverse the list. Which is an O(n) operation, so if you have a lot of nodes in your list say 10000 or more. It could take a long time to add an element.

So here’s what to do, we can create references to the front of the list and the end of the list to make adding to the list fast because here we can just add to the endpoints of the list without traversing. Effectively, what we just did was turn this into an O(1) insertion into the list.

Class LinkedList:
	def __init__(self):
		self.end = None

	def append(self, data):
		node = Node(data)
		if self.head:
			self.head.next = node
			self.head = node
		else:
			self.end = node
			self.head = node
                self.count += 1 # Notice we added the counter outside of the condition statements

We’re going to delete a node in our list by the data it holds. For example, if the node has data that contains “dogs” we will traverse the list until we encounter the node with “dog” then delete it from the list.

Here’s the thing, if we delete this node and it happens to be in the middle of the list we could cut the chain completely breaking any references to the next nodes in the list after the “dog” node. Terrible. So to fix this, we need to connect the node just before “dog” with the node next to “dog.” This will let us slice the “dog” node out of the chain but let us re-attach the chain back together.

Here’s how to do this in Python:

In our class LinkedList, we create another method called “delete”:

def delete(self, data):
	current = self.end
	prev = self.end
	while current:
		if current.data == data:
			if current == self.end:
				self.end = current.next
			else:
				prev.next = current.next
                        self.count -= 1 # Don't forget to decrement the size from our list.
                        return # We return early to break the loop since the value was found and the rechaining operation was performed
		prev = current
		current = current.next

Because we have to go through the list to search for the data that we want to delete. The performance of a large dataset is O(n).

Searching through the List

We’ll do two things to improve searching in our list for values. One we will be to create a generator object to hide the node implementation details.

Two, we will utilize the generator to allows us to search the data efficiently, because the generator will not load all the nodes into memory all at once this will prevent our processing of the data to be slowed down.

Here’s the code:

def iter(self):
    current = self.end
    while current:
         val = current.data
         current = current.next
         yield val # This will return the values of the list into a generator.

Now that we created a search generator. We can finally create our search operation.

def search(self, data):
    for node in self.iter():
        if data == node:
              return True
    return False

I hope this implementation was easy to understand, leave your suggestions in the comments below if you have any, and subscribe to the newsletter for more content coming your way!