Hi! If you are thinking where have you arrived and have no clue of whats going on then visit this page.

Here is the lecture on queues and linked lists by Prof Naveen Garg.

Learn Linked Lists in 10 minutes from the following video:

This video is also a very good source:

http://www.csanimated.com/animation.php?t=Linked_list

**1. Singly Linked List:**

A singly link list consists of one or more nodes with each node having a next pointer that points to the next node.

A very simple Node with all the operations might look like this in Python:

#node of a Singly Linked List class Node: #constructor def __init__(self): self.data = None self.next = None #method for setting the data field of the node def setData(self,data): self.data = data #method for getting the data field of the node def getData(self): return self.data #method for setting the next field of the node def setNext(self,next): self.next = next #method for getting the next field of the node def getNext(self): return self.next

Now that we have dealt with the nodes. Lets deal with the actual Linked List that contain these nodes.

The basic operations in a singly linked list are:

1. Traversing a Linked List

2. Inserting an element in the Linked List

3. Deleting an element in the Linked List

The code for implementing a Singly Linked List is as follows:

#A Singly Linked List class SinglyLinkedList: #constructor def __init__(self): self.head = None self.length = 0 #method for setting the head of the Linked List def setHead(self,head): self.head = head #method for inserting a new node at the beginning of the Linked List (at the head) def insertAtBeg(self,data): newNode = Node() newNode.setData(data) if self.length == 0: self.head = newNode else: newNode.setNext(self.head) self.head = newNode self.length += 1 #method for inserting a new node at the end of a Linked List def insertAtEnd(self,data): newNode = Node() newNode.setData(data) current = self.head while current.getNext() != None: current = current.getNext() current.setNext(newNode) self.length += 1 #method for inserting a new node at any position in a Linked List def insertAtPos(self,pos,data): if pos > self.length or pos < 0: return None else: if pos == 0: self.insertAtBeg(data) else: if pos == self.length: self.insertAtEnd(data) else: newNode = Node() newNode.setData(data) count = 0 current = self.head while count < pos-1: count += 1 current = current.getNext() newNode.setNext(current.getNext()) current.setNext(newNode) self.length += 1 #method for traversing and printing the Linked List def printList(self): current = self.head while current != None: print current.getData() current = current.getNext() #method for deleting a node having a certain data def delete(self,data): current = self.head previous = self.head if self.head.getData() == data: self.head = self.head.getNext() else: while (current.getData() != data): previous = current current = current.getNext() if current.getData() == data: previous.setNext(current.getNext()) else: return None if __name__ == "__main__": ll = SinglyLinkedList() ll.insertAtBeg(1) ll.insertAtBeg(2) ll.insertAtEnd(3) ll.insertAtPos(0, 4) ll.insertAtPos(4,5) ll.insertAtPos(2,9) ll.printList() ll.delete(9) print "Linked List After Deletion" ll.printList() print "Deleting the last element" ll.delete(5) ll.printList()

**2. Doubly Linked List**

A node in a doubly linked list can be defined using a class. It might look as follows:

class Node: #constructor def __init__(self): self.data = 0 self.next = None self.previous = None #method for setting the value of a node def setValue(self,value): self.data = value #method for getting the value of a node def getValue(self): return self.data #method for setting the next node of a node def setNext(self,next): self.next = next #method for getting the next node of a node def getNext(self): return self.next #method for setting the previous node of a node def setPrevious(self,previous): self.previous = previous #method for getting the previous node of a node def getPrevious(self): return self.previous

The basic operations in a Doubly Linked List is again

1. Insertion

2. Deletion

3. Traversal

The class for Doubly Linked List along with its operations is defined as follows:

class DoublyLinkedList: #constructor def __init__(self): self.head = None #head of the list self.length = 0 #length of the list #method for inserting at the beginning of the list def insertAtBeg(self,value): newNode = Node() newNode.setValue(value) newNode.setNext(None) newNode.setPrevious(None) if self.length == 0: self.head = newNode self.length += 1 else: newNode.setNext(self.head) self.head.setPrevious(newNode) self.head = newNode self.length += 1 #method for inserting a node at the end def insertAtEnd(self,value): newNode = Node() newNode.setValue(value) current = self.head while(current.getNext() != None): current = current.getNext() newNode.setNext(current.getNext()) newNode.setPrevious(current) current.setNext(newNode) self.length += 1 #method for inserting a node at the middle def insertAtMid(self,pos,value): newNode = Node() newNode.setValue(value) current = self.head count = 0 while(count < pos-1): current = current.getNext() count += 1 current.getNext().setPrevious(newNode) newNode.setNext(current.getNext()) current.setNext(newNode) newNode.setPrevious(current) self.length += 1 #method for traversing and printing the list def printList(self): current = self.head while current != None: print current.getValue() current = current.getNext()

**3. Circular Linked List**

Here is a list of problems related to Linked Lists.

1. Find the nth node from the end of a singly linked list.

2. Write a program to implement ordered singly linked lists.

3. Write a program to detect a cycle in a linked list.

Pingback: Data Structures and Algorithms | codeatsociallywired