Linked Lists

Agenda

1. The LinkedList and Node classes
2. Implementing append
3. Implementing deletion
4. Bidirectional links
5. Incorporating a cursor
6. Run-time analysis
7. Closing remarks

# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"

1. The LinkedList and Node classes

class LinkedList:
    class Node:
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    
    def __init__(self):
        self.head = None
        self.count = 0
    
    def prepend(self, value):   #O(1)
        # create node
        # make new node point to old first item
        # fix head to the new node
        #increment count
        # this works even if the LinkedList is empty
        self.head  = LinkedList.Node(value, self.head )
        self.count+=1
    
    def __len__(self):
        return self.count
        
    def __iter__(self):
        n = self.head
        while n:    # while n!=None
            yield n.val
            n = n.next
    
    def __repr__(self):
        return '[' + ', '.join(str(x) for x in self) + ']'

lst = LinkedList()
for i in range(10):
    lst.prepend(i)
lst

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

2. Implementing append

Option 1

class LinkedList (LinkedList): # note: using inheritance to extend prior definition
    def append(self, value):
        # find the last node, walk to it O(n) 
        # temp is the pointer to the last node
        # make new node
        # make temp.nect= newnode
        #  need a special case for empty LinkedList
        if not self.head:
            self.prepend(value)
        else:  
            temp=self.head    
            # the while fails of temp is None
            while temp.next:   #only move temp forward if the next node exists
                temp=temp.next
            # temp is pointing the last node
            temp.next=LinkedList.Node(value, None)
            self.count+=1

lst = LinkedList()
for i in range(10):
    lst.append(i)
lst

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Option 2

class LinkedList (LinkedList):
    def __init__(self):   # Linked List stores a pointer to first element and
        # pointer to last element
        self.head = self.tail = None
        self.count = 0
        
    def prepend(self, value):
# special case needed if LinkedList is empty, must make self.tail point to new node also
        self.head  = LinkedList.Node(value, self.head )
        self.count+=1
        if self.tail==None:   # if not self.tail
            self.tail=self.head
        
    def append(self, value):   #O(1)
        # special case for empty linked list
        if not self.head:
            self.prepend(value)
        else:   # not empty LinkedList
            # make self.tail.next point to new node
            # then make self.tail point to new node
            self.tail.next=LinkedList.Node(value, None) #makes the old tail point to the new node
            self.tail=self.tail.next # fixes the tail on the new last node
            self.count+=1

lst = LinkedList()
for i in range(10):
    lst.prepend(i)
lst
lst.head.val
lst.tail.val

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

9

0

lst = LinkedList()
for i in range(10):
    lst.append(i)
lst

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3. Implementing deletion

Deleting the head

class LinkedList (LinkedList):
    def del_head(self):
        assert(len(self) > 0)   #if linkedlist empty
        # self.head needs to point to 2nd node
        # old first node . next needs to be None
        #decrement count
        #spcial case for 0 or 1 node
        temp=self.head
        self.head=self.head.next
        temp.next=None # good practice to clean up links no longer needed
        self.count-=1
        # if we just deleted the last node?
        if self.count==0:
            self.tail=None
        

lst = LinkedList()
for i in range(10):
    lst.append(i)
lst.del_head()
lst.del_head()
lst

[2, 3, 4, 5, 6, 7, 8, 9]

Deleting the tail

class LinkedList (LinkedList):
    def del_tail(self):
        assert(len(self) > 0)
        # make the 2nd to last node point to None  (WALK TO GET THERE)
        # make the self.tail point to 2nd to last node
        if self.count>1:
            temp = self.head
            # i need to walk temp to stop at the node BEFORE the last node
            # how do I know what the last node is?
            #YUCK
            while temp.next!=self.tail:  # temp.next is not self.tail
                temp=temp.next
            # temp is pointing to 2nd to last node
            temp.next=None
            self.tail=temp
        else:
            #  only one node
            self.head=None
            self.tail=None
        self.count-=1         
        
        

lst = LinkedList()
for i in range(10):
    lst.append(i)
lst.del_tail()
lst.del_tail()
lst

[0, 1, 2, 3, 4, 5, 6, 7]

lst.del_tail()
lst.del_tail()
lst.del_tail()
lst.del_tail()
lst.del_tail()
lst.del_tail()
lst.del_tail()
lst

[0]

lst.del_tail()
lst

[]

4. Bidirectional links (Doubly-linked list)

class LinkedList:
    class Node:
        def __init__(self, val, prior=None, next=None):
            self.val = val
            self.prior = prior
            self.next  = next
    
    def __init__(self):   # constructor for LinkedList  
        self.count = 0
        self.head= LinkedList.Node(None)
        self.head.prior=self.head
        self.head.next=self.head
    #   self.head= LinkedList.Node(None,prior=self.head,next=self.head)   self.head is none
        
    def prepend(self, value):     #  O(1)
        #                                  dummy            OLD FIRSTNODE
        a = LinkedList.Node(val=value, prior=self.head, next=self.head.next)
        self.head.next.prior=a
        self.head.next=a
        self.count += 1
        
    def append(self, value):   # O(1)
                                #            OLD LAST NODE         dummy
        a = LinkedList.Node(val=value, prior=self.head.prior, next=self.head)
        self.head.prior.next=a
        self.head.prior=a
        self.count += 1
        
    def __getitem__(self, idx): # O(N) 
        assert idx >= 0 and idx < len(self)  # BETTER, NORMALIZE INDEX FIRST
        a = self.head.next    #  pointer to the first actual node
        for i in range(idx):
            a=a.next
        return a.val
        
    def del_head(self):
        assert(len(self) > 0)
        a = self.head.next   # pointer to the node to delete
        # need to make the node before "a" point to the node after "a"
        a.prior.next=a.next
        # need to make the node after "a" point to the node before "a"
        a.next.prior=a.prior
        # remove "a"s next and prior
        a.next=None
        a.prior=None
        self.count-=1
        # the above code works at any valid node in the linked list
        # if you have a pointer "a" to it
        
    def __len__(self):
        return self.count
        
    def __iter__(self):
        n = self.head.next
        while n is not self.head:
            yield n.val
            n = n.next
    
    def __repr__(self):
        return '[' + ', '.join(str(x) for x in self) + ']'

lst = LinkedList()
for i in range(10):
    lst.prepend(i)
for i in range(10):
    lst.append(i)
lst

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

lst[0]
lst[10]

9

0

lst.del_head()
lst
lst.del_head()
lst

[8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

5. Incorporating a cursor

class LinkedList (LinkedList):
    
    def __init__(self):   # add a cursor attribute
        self.head = LinkedList.Node(None)
        self.head.prior = self.head.next = self.head
        self.count = 0
        self.cursor=self.head   #  add another attribute to LinkedList
                
    def cursor_set(self, idx):
        assert idx >= 0 and idx < len(self)   # valid idx
        self.cursor=self.head.next   # pointing to idx=0
        for i in range(idx):
            self.cursor=self.cursor.next        

    def cursor_insert(self, value): # O(1)
        #cursor_insert: inserts a new value after the cursor and 
        #sets the cursor to the new node
        assert self.cursor is not self.head   #cursor is pointing to a valid position
        
        a = LinkedList.Node(val=value, prior=self.cursor, next=self.cursor.next)
        self.cursor.next.prior=a
        self.cursor.next=a
        self.cursor=a
        self.count += 1
        
    def cursor_delete(self): # O(1)
        
        assert self.cursor is not self.head
   #cursor_delete: deletes the node the cursor refers to 
#and sets the cursor to the following node   
        a=self.cursor
        a.prior.next = a.next
        a.next.prior = a.prior
        self.cursor=self.cursor.next
        a.next=None
        a.prior=None
        self.count-=1

lst = LinkedList()
for i in range(10):
    lst.append(i)
lst

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

lst.cursor_set(4)
for x in 'abcd':
    lst.cursor_insert(x)
lst
lst.cursor.val

[0, 1, 2, 3, 4, a, b, c, d, 5, 6, 7, 8, 9]

'd'

lst.cursor_set(8)
for _ in range(4):
    lst.cursor_delete()
lst

[0, 1, 2, 3, 4, a, b, c, 8, 9]

6. Run-time analysis

Run-time complexities for circular, doubly-linked list of $N$ elements:

• indexing (position-based access) = $O(?)$
• search (unsorted) = $O(?)$
• search (sorted) = $O(?)$ --- binary search isn't possible!
• prepend = $O(?)$
• append = $O(?)$
• insertion at arbitrary position: traversal = $O(?)$ + insertion = $O(?)$
• deletion of arbitrary element: traversal = $O(?)$ + deletion = $O(?)$

7. Closing remarks

Lab 5, 1.Subscript-based access (if time permits)