Linked list in python
Published: 2021-01-19 10:56:55

# Linked List Data Structure in Python</h1>
 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.