Linked List | Data Structure

In computer science, Linked List is a basic and linear type data structure like Array. Both are used to store a collection of elements. But there is a difference between Array and Linked List. But In this article, I will write all about Linked List. You can read my article about the Array if you are interested.

Introduction

A Linked List is a collection of nodes. In array, we know that every element is stored sequentially in memory. But nodes are not stored sequentially in the memory address. In a Linked List, each node is connected using reference. The first question is, What is a node? We can think a node is an element of a Linked List. It contains two fields. One is for value, and another is for storing the reference of the next node. If there is no next node, this value will be null.

Suppose we have a Linked List that has two nodes, Which values are A, B. And A is the head node of this list, from where the list will start. A node contains another field, which stores the next node memory address. In this case, the next node is B. So using this reference, A connected with B.

If we have any other node, B will contain that node reference, but this time B will point to null instead of pointing to the next node. Let’s see a visual example.

After the visual representation, let’s see how can we implement a node into code. The example will be in Python.

So, we will create a class for the node, and using that class, we will create a node object as many as we need. The class will have two fields. One is for value (val), and another is for the next node reference(next). Let’s see the code example of the visual representation.

class Node():

	def __init__(self, val=None, next=None):
		self.val = val
		self.next = next
		

A = Node('A')
B = Node('B')

print(A.val) # A
print(B.val) # B
print(A.next) # None

A.next = B

print(A.next) # Node('B')
print(A.next.val) # B

Note: There are two types of Linked List. Singly and Doubly Linked List. Will will talk about a singly Linked List. If You can understand it, doubly Linked List will be easy for you. The actual difference is, in a Singly List, we can traverse only forward. On the other hand, in a Doubly List, we can traverse both ways forward and backward.

Linked List and Operations

So we already know how to create a node. But creating a node is not sufficient. Also, this way, creating a node and connecting a node is very tedious. There is a better way to do this. And we are also going to learn about some basic operations to run on Linked List.

Now, we will be going to create a class called Linked List. This class is to illustrate the whole Linked List and its operations. Because of this class, we don’t need to create a node and print a value manually of a list as we did before.

class LinkedList():
	
	def __init__(self):
		self.head = None # The head is for tracking the first node.

We created the class Linked List. The head node will be the first node, and through this node, we will start to traverse the whole list. Initially, the head value is None, and that means our Linked List is empty.

Insert

So, we have Node and Linked List. Now we will insert a node into the list. For that, we will define a method so that we don’t have to do this task manually. With this method, we will insert a node into the end of the List. Let’s see the code first.

class LinkedList():
	
	def __init__(self):
		self.head = None # The head is for tracking the first node.

	# Insert 
	def insert(self, val):
		new_node = Node(val) # Create a new node with the given value
		
		if self.head:
			current = self.head
			while current.next:
				current = current.next
				
			current.next = new_node
		else:
			self.head = new_node

list = LinkedList()
list.insert(1) # Provide the node Value as a parameter

In the insert method, first, we create a new node with the given value. And then we check the head node. If the head node is not empty, we go to the end of the list using a loop. Then we add the new node as the last node’s next value. If the head node is empty, we just set the new node as the head. Pretty simple.

Traverse

Traversing means visiting. At this point, we know how to insert a node into a List. But often, we need to see the Linked List values. And this is important. Let’s see the code for traversing all nodes and how to display it.

class LinkedList():
	
	def __init__(self):
		self.head = None # The head is for tracking the first node.

        # Assume that insert method is hidden. 

	# traverse
	def traverse(self):
		current = self.head
		nodes = []
		
		while current:
			nodes.append(str(current.val))
			current = current.next
		
		nodes.append('None')
		return '->'.join(nodes)


list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)

print(list.traverse()) # 1->2->3->None

This method is also pretty simple. First, we store the head node in the current variable. Then we create an empty array to store all values (list in python). Then we run a loop until the current variable is not null. The current variable becomes null when it reached the ends or if the Linked List is empty. If the variable is not null, we append the value of it in the array. Then using the next property of the Node class, we move one step forward. And assign it to the current variable. If the current variable value is null, the loop will stop.

The array is just for display purposes, nothing else. After the array, we added ‘None’ to the array. This one is also for display purposes. Because the last node of a Linked List points to null.

Note: In python, None is equivalent to null.

Search

Traversing is easy in a Linked List. If you know how to traverse, searching will be easier for you. We use a loop for traversing. We have to put an extra check in the loop when we want to search for a node. Which is our searching value is equal to the current node value or not. Simple, right? Let’s see the code.

class LinkedList():
	
	def __init__(self):
		self.head = None # The head is for tracking the first node.

        # Assume that insert method is hidden.
        # Assume that traverse method is hidden. 
	
	# search
	def search(self, val):
		
		current = self.head
		
		while current:
			if val == current.val:
				return True
			
			current = current.next
		
		return False


list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)

print(list.search(2)) # true
print(list.search(5)) # False

Delete

When we want to remove a node from a Linked List, what should we do? Suppose We have a Linked List with the value 1, 2, and 3. Here node 1’s next field points to node 2. And node 2 points to node 3. Now, we want to delete Node 2. To do that, we will detach node 2 from the Linked List. For that, we will change node 1’s next’s field value, the value will be 2’s next node. In this case, it is 3. The formula is previous_node.next = deleted_node.next.

If we want to delete the head, we will just set the head’s next node to the head.

Let’s see the code. My explanation is horrible. 😀

class LinkedList():
	
	def __init__(self):
		self.head = None # The head is for tracking the first node.

        # Assume that insert method is hidden.
        # Assume that traverse method is hidden.
        # Assume that search method is hidden.

	# delete 
	def delete(self, target):
		if self.head == None:
			print('List is empty')
			return
		
		if self.head.val == target:
			self.head = self.head.next
		
		previous = self.head
		current = self.head
		
		while current:
			if current.val == target:
				previous.next = current.next
				return
			
			previous = current
			current = current.next
		
		print(f'Node with data {target} not found')
		

list = LinkedList()
list.insert(1)
list.insert(2)
list.insert(3)

print(list.traverse()) # 1->2->3->None
list.delete(2)
print(list.traverse()) # 1->3->None
list.delete(5) # Node with data 5 not found

These are the basics of Linked List Data Structure. There are many things to do using Linked List. And many Linked List operations I did not cover.

Thanks for reading the whole article. I hope if you are a beginner, this article helps you.

Tags: Data StructureLinked ListSingly Linked List