Python Data structures : Linked Lists

Linked lists is a linear data structure in which each element is a node that comprise of data and pointer to next node.
like this:

In arrays we can access the elements of the list by using index numbers. But suppose we want to insert tan element at the second position of the list , so we need to shift all the elements of list one step towards right to push just a single value. Where as in Linked list implementation we will just add a new node storing the data we want to insert and change pointer at first position towards this new node and pointer of this new node towards the initially second element. In same way we can define the remove function, the pointer from current node will point towards next to next node. And the next node will be automatically removed from Linkedlist.

So for implementing linked list we will first create a node class:

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

Next we will create a class LinkedList in which we define various operations on linked  lists:

class LinkedList(object):

    def __init__(self):
        self.head = None
        self.size =0


    def extend(self, seq = None):
        """extends list with the given sequence"""

        for i in range(0, len(seq)):
            node = Node(seq[i])
            self.size +=1
            node.next = self.head
            self.head = node

    def append(self, item):
        """append item to the end of list"""
        node = Node(item)
        node.next = self.head
        self.head = node
        self.size += 1

    def printdata(self):
        """print elements of linked list"""
        node = self.head 
        while node:
            print node.data
            node = node.next

    def __iter__(self):
        node = self.head
        while node:
            yield node.data
            node = node.next

    def __contains__(self, item):
        """checks whether given item in list"""
        node = self.head 
        while node:
            if node.data == item:
                return True
            node = node.next


    def len(self):
        """returns the length of list"""
        return self.size


    def remove(self, item):
        """removes item from list"""
        node = self.head
        current = self.head.next
        if node.data == item:
            self.size -= 1
            self.head = current
            current = current.next
        while current:
            if current.data == item:
                current = current.next
                node.next = current
                self.size -= 1
            node = current
            current = current.next




    def __str__(self):
        return  str(self.data) + str(self.size)




Then we will define our main()  function and give inputs to the  Linked list.

def main():
    llist = LinkedList()

    llist.extend([98,52,45,19,37,22,1,66,943,415,21,785,12,698,26,36,18,
    97,0,63,25,85,24])

    print "Length of linked list is ", llist.len()

    llist.append(222)

    print "Length of linked list is ", llist.len()

    llist.remove(22)

    print "Elements of linked list  \n", llist.printdata()
    print "Length of linked list is ", llist.len()

   ## Search for an element in list   
    while True:
        item = int(raw_input("Enter a number to search for: "))
        if item in llist:
            print "It's in there!"
        else:
            print "Sorry, don't have that one"

if __name__ == "__main__":

    main()




.