Linked List¶

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

In [2]:

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

In [3]:

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
        
        
        
    '''Append the element'''
    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element
            
            
            
    '''get the element form a given position'''
    def get_position(self, position):
        current = self.head
        count = 1
        if self.head:
            while count < position:
                current = current.next
                count += 1
            return current
        else:
            return None

    '''incert a new element at a given position'''
    def insert(self, new_element, position):
        current = self.head
        count = 1
        if position == 1:
            new_element.next = current
            self.head = new_element
        else:
            while count < position - 1:
                current = current.next
                count += 1
            new_element.next = current.next
            current.next = new_element

            
    '''Delete the first node with a given value'''
      
    def delete(self, value):
        current = self.head
        prev = None
        while current and current.value != value:
            prev = current
            current = current.next
        if current is not None:
            if current == self.head:
                self.head = self.head.next
            else:
                prev.next = current.next

In [4]:

# Test cases
# Set up some Elements
e1 = Element(101)
e2 = Element(203)
e3 = Element(304)
e4 = Element(494)

In [5]:

# Start setting up a LinkedList
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)

In [12]:

# Test get_position
# Should print 3
print(ll.head.next.next.value)

In [15]:

# Should also print 3
print(ll.get_position(4).value)

In [8]:

# Test insert
ll.insert(e4, 3)
# Should print 4 now
print (ll.get_position(3).value)

In [9]:

# Test delete
ll.delete(1)
# Should print 2 now
print (ll.get_position(1).value)

In [10]:

# Should print 4 now
print (ll.get_position(2).value)

In [64]:

# Should print 3 now
print (ll.get_position(3).value)

Assignment¶

Create a Linked List to store 10000 random numbers and
delete odd positioned numbers and
insert value '555'
write a function to find a sum of all values and calculate sum

In [17]:

import random as random
E =[]
for k in range(100):
    E.append(Element(random.randint(1,10000)))

In [18]:

ll = LinkedList()

In [19]:

for  k in range(100):
    ll.append(E[k])

In [21]:

for i in range(100):
    print(ll.get_position(i).value)

This is not a solution. Do it yourself.....¶

In [ ]: