Linked list implementation

In this post we can show how to implement a linked list in python.

In computer science , a linked list is a data structure used for collecting a sequence of objects, which allows efficient addition, removal and retrieval of elements from any position in the sequence. It is implemented as nodes, each of which contains a reference (i.e., a link) to the next and/or previous node in the sequence.

        A linked list whose nodes contain two fields: an integer value and a link to the next node

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data structures, including stacks, queues, associative arrays, and symbolic expressions.

The principal benefit of a linked list over a conventional array is that the list elements can easily be added or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list.

In python, we can simply implement a linked list by using class.

class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # pointer to next node
class linked_list:
    def __init__(self):
        self.pointer = None
    def add_node(self, data):
        new_node = node() # create new node
        new_node.data = data
        new_node.next = self.pointer # Link the pointer to the  previous node
        self.pointer = new_node #  set the current node to the new one.
    def list_print(self):
        node = ll.pointer
        while node:
            print node.data
            node = node.next
ll = linked_list() # Create an object of class 'Linked_list'
ll.add_node(21)
ll.add_node(32)
ll.add_node(45)
ll.list_print() # Print the node data

 Output:

anoop@anoop-laptop:~$ python linked.py
45
32
21