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):
        self.head=LinkedList.Node(value, self.head)    # calling Node constructor
        self.count+=1
    
    def __len__(self):
        return self.count
        
    def __iter__(self):
        n = self.head
        while n:
            yield n.val
            n = n.next
    
    def __repr__(self):   # repr uses __iter__
        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):   # need to walk all the way to the end, then insert node
        # need a while loop, but cannot use the __iter__ which walks all the way past the last node
        n=self.head   # n is the pointer to walk the linked list
        # must add special case for empty linked list
        if self.count==0:   #self.head=None
            self.head=LinkedList.Node(value, None)
            #self.prepend(value)
        else:
            while n.next!=None:   # this will stop when n is pointing to last actual node
                n=n.next
            n.next=LinkedList.Node(value, None)
            
        self.count+=1
        # Option 1 append runtime  O(size of list)
        

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):
        self.head = self.tail = None
        self.count = 0
        
    def prepend(self, value):
        # if only have a self.head, this prepend is fine even of empty
        #self.head=LinkedList.Node(value, self.head)    # calling Node constructor
        #self.count+=1
        # if have self.head and self.tail, and list is empty, special case
        if self.count==0:
            self.head=self.tail=LinkedList.Node(value, self.head) 
            self.count+=1
        else:
            self.head=LinkedList.Node(value, self.head)    # calling Node constructor
            self.count+=1
        
    def append(self, value):    # O(1)   does not depend on list length
        if self.count==0:    # list empty
            self.prepend(value)  # if list is empty, prepend and append are the same
        else:
        # make the new node
        #  make self.tail.next point to the new node
        #make self.tail point to the new node
        # increment self.count  
            a = LinkedList.Node(value)
            self.tail.next = a
            self.tail = a
            self.count+=1
        
        

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)   # empty list, exception on call to del_head
        # if list has only one element, make head and tail none, decrement count
        if self.count==1:
            self.head=None
            self.tail=None
            self.count=0
        
        # if the list has elements, 
        #   make self.head point to self.head.next
        #   self.count --
        else:
            self.head = self.head.next
            self.count-=1

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

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

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

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

Deleting the tail

class LinkedList (LinkedList):
    def del_tail(self):
        assert(len(self) > 0)
        if self.count==1:
            self.del_head()
        else:
            n=self.head
            while n.next is not self.tail:
                n=n.next
            # n is pointing to node before the tail
            #n=self.head
            #for i in range(self.count-1):
            #    n=n.next
            self.tail=n
            n.next=None
            self.count-=1

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

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

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

[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.del_tail()
lst

[]

lst.del_tail()

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-11-4e7f3538e9c5> in <module>
----> 1 lst.del_tail()

<ipython-input-8-d3287fa03527> in del_tail(self)
      1 class LinkedList (LinkedList):
      2     def del_tail(self):
----> 3         assert(len(self) > 0)
      4         if self.count==1:
      5             self.del_head()

AssertionError: 

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):   #  constructing an empty list with 1 dummy node
        self.count = 0             # val, prior, next
        self.head = LinkedList.Node(None, None, None)
        self.head.next=self.head
        self.head.prior=self.head
        
    def prepend(self, value):
                            # val, prior, next
        newNode=LinkedList.Node(value,prior=self.head ,next= self.head.next )
        self.head.next.prior=newNode
        self.head.next=newNode
        self.count += 1
        
    def append(self, value):
        newNode=LinkedList.Node(value, prior= self.head.prior, next=self.head)
        # the next of old item before it needs to point to newNode
        self.head.prior.next=newNode
        # the prior of the olf item after it needs to point to newNode
        self.head.prior=newNode
        self.count += 1

    def _normalize_idx(self, idx):
        nidx = idx
        if nidx < 0:
            nidx += len(self)
            if nidx < 0:
                nidx = 0
        return nidx
        
    def __getitem__(self, idx): # O(N) 
#        assert idx >= 0 and idx < len(self)  # BETTER, NORMALIZE INDEX FIRST
        assert(isinstance(idx,int))
        nidx = self._normalize_idx(idx)
        if nidx > len(self):
            raise IndexError
        # need to walk
        else:
            n = self.head.next   #  pointing to index position 0, first element
            # or if list is empty, n is the dummy node (val=None)
            for i in range(nidx):
                n=n.next
            return n.val    # if list is empty, this returns dummy val None
    
    def del_head(self):
        assert(len(self) > 0)
        pass
        
    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
lst[5]
lst[12]
lst[-1]
lst[-2]

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

4

2

9

8

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  # intiailly the cursor is the dummy node
                
    def cursor_set(self, idx):
        assert idx >= 0 and idx < len(self)
        # walk to node number idx
        #  idx=0 is first actual node, self.head.next
        self.cursor=self.head.next   # idx=0
        for i in range(idx):
            self.cursor=self.cursor.next
    
    def cursor_insert(self, value): # O(1)  inserts after the cursor
        assert self.cursor is not self.head
        n = LinkedList.Node(value, prior=self.cursor, next=self.cursor.next)
        self.cursor.next.prior=n
        self.cursor.next=n
        self.count+=1
    
    def cursor_delete(self): # O(1)  deletes what the cursor is pointing to
        # updates the cursor to point to the next node
        assert self.cursor is not self.head
        n =self.cursor   # n is node to delete
        self.cursor=self.cursor.next
        # special case if deleting the last item, cursor is pointing to it
        if self.cursor == self.head:
            self.cursor=self.cursor.next
        n.prior.next=n.next
        n.next.prior=n.prior
        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

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

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

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

6. Run-time analysis

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

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

7. Closing remarks

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