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:

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:

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:

```

#constructor
def __init__(self):
self.length = 0

#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:
else:
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)

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
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):
while current != None:
print current.getData()
current = current.getNext()

#method for deleting a node having a certain data
def delete(self,data):

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.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)

ll.printList()

print "Deleting the last element"
ll.delete(5)
ll.printList()

```

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.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.length += 1
else:
self.length += 1

#method for inserting a node at the end
def insertAtEnd(self,value):
newNode = Node()
newNode.setValue(value)

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)
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):
while current != None:
print current.getValue()
current = current.getNext()

```

Here is a list of problems related to Linked Lists.

# Detecting Cycles in Linked List (Hare and Tortoise)

The problem is as follows:
Check whether the given linked list is NULL terminated or ends in a cycle.

Sample Input: 1->2->3->4->5->6->7->8->3
where the numbers 1,2… are the positions in the linked list instead of actual entries.
The node at the 8th position again points to the node at the 3rd position forming a cycle.

Sample Output: True

A very good discussion of how the cycles are detected can be found in wikipedia over here:http://en.wikipedia.org/wiki/Cycle_detection

The Floyds’ algorithm commonly referred as tortoise and hare method is often used for detecting cycles. It could be an interesting read. We can think of a hare and a tortoise running on a track. The faster running hare will catch up with the tortoise if they are running in a loop.

The basic algorithm is as follows:
Step 1. Start Tortoise and Hare at the first node of the List.
Step 2. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare one step forward.
Step 3. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare and Tortoise one step forward.
Step 4. If Hare and Tortoise pointing to same Node return, we found loop in the List.

```'''Complexity
Space : O(n) Time: O(1)'''

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

def setData(self,data):
self.data = data

def getData(self):
return self.data

def setNext(self, next):
self.next = next

def getNext(self):
return self.next

def __init__(self):

def isEmpty(self):

def insertAtBeg(self,item):
node = Node(item)

def length(self):
count = 0
while current != None:
count += 1
current = current.getNext()
return count

def search(self,item):
found = False
if current.getData() == item:
found = True
else:
current = current.getNext()

return found

def insertAtEnd(self,item):

while current.getNext() != None:
current = current.getNext()

node = Node(item)
current.setNext(node)

def insertBeforeItem(self,inItem,item):
previous = None
found = False
stop = False

if current.getData() == item:
found = True
stop = True
else:
previous = current
current = current.getNext()

node = Node(inItem)
previous.setNext(node)
node.setNext(current)

def insertAfterItem(self,inItem,item):

found = False
stop = False

if current.getData() == item:
found = True
stop = True
else:
#                previous = current
current = current.getNext()
successor = current.getNext()
node = Node(inItem)
current.setNext(node)
node.setNext(successor)

def printList(self):

while current != None:
print current.getData()
current = current.getNext()

def remove(self,item):
found = False
previous = None

if current.getData() == item:
print current.getData()
print previous.getData()
found = True
previous.setNext(current.next)
else:
previous = current
current = current.getNext()

def induceCycle(self,end,start):
stop = False
endnodeFound = False
endnodePointer = None
count = 0
while current!= None and not stop:
count += 1
if count == end:
endnodeFound = True
endnodePointer = current.getNext()

else:
if count == start:
stop = True
else:
current = current.getNext()

current.setNext(endnodePointer)

def detectCycle(self):

while (hare and tortoise):
hare = hare.getNext()
if (hare == tortoise):
return True

if hare == None:
return False

hare = hare.getNext()
if (hare == tortoise):
return True

tortoise = tortoise.getNext()

if __name__ == "__main__":
ll.insertAtBeg(1)
ll.insertAtBeg(2)
ll.insertAtEnd(3)
ll.insertBeforeItem(4, 3)
ll.insertAfterItem(5, 1)
ll.insertAtEnd(6)
ll.insertAtEnd(8)
ll.insertAtEnd(7)

ll.printList()

ll.induceCycle(2, 8)
print ll.detectCycle()
```

# Getting nth node of a linked list from the end

The problem is as follows:
Find the nth node from the end of a singly linked list.

Sample Input : 2->1->5->4->3 and n = 3
Sample Output : 5

```
'''Complexity
Space:  O(n) and Time: O(1)'''

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

def setData(self,data):
self.data = data

def getData(self):
return self.data

def setNext(self, next):
self.next = next

def getNext(self):
return self.next

def __init__(self):

def isEmpty(self):

def insertAtBeg(self,item):
node = Node(item)

def length(self):
count = 0
while current != None:
count += 1
current = current.getNext()
return count

def search(self,item):
found = False
if current.getData() == item:
found = True
else:
current = current.getNext()

return found

def insertAtEnd(self,item):

while current.getNext() != None:
current = current.getNext()

node = Node(item)
current.setNext(node)

def insertBeforeItem(self,inItem,item):
previous = None
found = False
stop = False

if current.getData() == item:
found = True
stop = True
else:
previous = current
current = current.getNext()

node = Node(inItem)
previous.setNext(node)
node.setNext(current)

def insertAfterItem(self,inItem,item):

found = False
stop = False

if current.getData() == item:
found = True
stop = True
else:
#                previous = current
current = current.getNext()
successor = current.getNext()
node = Node(inItem)
current.setNext(node)
node.setNext(successor)

def printList(self):

while current != None:
print current.getData()
current = current.getNext()

def remove(self,item):
found = False
previous = None

if current.getData() == item:
print current.getData()
print previous.getData()
found = True
previous.setNext(current.next)
else:
previous = current
current = current.getNext()

def nthNodeFromEnd(self,n):

if self.isEmpty():
print "There are no items in the list"
return

if n > self.length():
print "N is greater than the lenght of the list and is not possible to fetch it"
return

count = 0
while count < n and current != None:
count += 1
current = current.getNext()

while current != None:
previous = previous.getNext()
current = current.getNext()

return previous.getData()

if __name__ == "__main__":
ll.insertAtBeg(1)
ll.insertAtBeg(2)
ll.insertAtEnd(3)
ll.insertBeforeItem(4, 3)
ll.insertAfterItem(5, 1)
print "The linked list is as follows:"
ll.printList()
print "\n\n"
print "The 2nd item from the end is:",ll.nthNodeFromEnd(2)
print "The 3rd item from the end is:", ll.nthNodeFromEnd(3)

```

```class Node:
def __init__(self,data):
self.data = data
self.next = None

def setData(self,data):
self.data = data

def getData(self):
return self.data

def setNext(self, next):
self.next = next

def getNext(self):
return self.next

def __init__(self):

def isEmpty(self):

def length(self):
count = 0
while current != None:
count += 1
current = current.getNext()
return count

def search(self,item):
found = False
stop = False
if current.getData() == item:
found = True
else:
if current.getData() > item:
stop = True
else:
current = current.getNext()

return found

def insertion(self,item):
node = Node(item)
else:
previous = None
stop = False

while current != None and not stop:
if current.getData() > item:
stop = True
else:
previous = current
current = current.getNext()

node = Node(item)
previous.setNext(node)
node.setNext(current)

def remove(self,item):
found = False
previous = None

if current.getData() == item:
print current.getData()
print previous.getData()
found = True
previous.setNext(current.next)
else:
previous = current
current = current.getNext()

def printList(self):

while current != None:
print current.getData()
current = current.getNext()

if __name__ == "__main__":