In [13]:

    

"""A linked list is a data structure with elements connected by pointers.
They can change size and allocated memory as the list grows.
Arrays have an advantage in taking O(1)(constant time) to access elements where linked lists are O(n).
Linked lists also waste some space O(n) to store pointers
Linked lists have the advantage in being able to change size in constant time where arrays are O(n) if non-full
"""


    

    
Out[13]:





'A linked list is a data structure with elements connected by pointers.\nThey can change size and allocated memory as the list grows.\nArrays have an advantage in taking O(1)(constant time) to access elements where linked lists are O(n).\nLinked lists also waste some space O(n) to store pointers\nLinked lists have the advantage in being able to change size in constant time where arrays are O(n) if non-full\n'

In [98]:

    

#linked list of integers

#NODE of the singly linked list
class Node:
    #constructor
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
    #method to set data of node
    def setData(self, data):
        self.data = data
    #method to get data from node
    def getData(self):
        return self.data
    #set next field
    def setNext(self,next):
        self.next = next
    #get next field of node
    def getNext(self):
        return self.next
    #return true if node points to something
    def hasNext(self):
        return(self.next != None)


    

In [99]:

    

#the LINKED LIST
#want at least insert, size, search, delete
class LinkedList:
    #initialize list with no nodes or head
    def __init__(self, head=None):
        self.head = head#head node
        self.length = 0
    def size(self): #O(N) since we visit each node
        current = self.head
        count = 0
        while current!=None:
            count += 1
            current = current.getNext()
        return current
    def insert(self,data):#at front O(1)
        new_node = Node()
        new_node.setData(data)
        if self.length==0:
            self.head = new_node
        else:
            new_node.setNext(self.head)
            self.head = new_node
        self.length+=1
    def search(self, data):
        current = self.head
        found = False
        while (current is not None) and(found is False):
            if current.getData() == data:
                found = True
            else:
                current = current.getNext()
        if current is None:
            print("Value is not present")
        return current
    def delete(self, data):
        current = self.head
        previous = None
        found = False
        while (current is not None) and (found is False):
            if current.getData() == data:
                found = True
                self.length-=1
            else:
                previous = current
                current = current.getNext()
        if current is None:
            print("Value is not present")
        if previous is None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())


    

In [100]:

    

#play with an example
mll = LinkedList()


    

In [101]:

    

type(mll)


    

    
Out[101]:





__main__.LinkedList

In [102]:

    

mll.insert(1)


    

In [103]:

    

mll.insert(2)


    

In [104]:

    

mll.search(2).getData()


    

    
Out[104]:





2

In [105]:

    

mll.insert(3)


    

In [106]:

    

mll.delete(2)


    

In [107]:

    

mll.search(2)


    

    




Value is not present

In [108]:

    

mll.length


    

    
Out[108]:





2

In [109]:

    

mll.insert(4)


    

In [110]:

    

mll.length


    

    
Out[110]:





3

In [113]:

    

mll.search(4).getData()


    

    
Out[113]:





4

In [ ]:

    




    

In [ ]: