Linked Lists

Agenda

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

1. The LinkedList and Node classes

In [87]:
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, next=self.head) #creating a new node; right-hand side evaluated first
        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):
        return '[' + ', '.join(str(x) for x in self) + ']'
In [88]:
lst = LinkedList()

for i in range(10):
    lst.prepend(i)
    
lst
Out[88]:
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

2. Implementing append

Option 1

In [89]:
class LinkedList (LinkedList): # note: using inheritance to extend prior definition
    def append(self, value):
        if not self.head:
            self.prepend(value)
        else:
            n = self.head
            while n.next: 
                n = n.next
            
            n.next = LinkedList.Node(value)
            self.count += 1
In [90]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst
Out[90]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [91]:
len(lst)
Out[91]:
10

Option 2

In [92]:
# how to make append operation O(1)?

class LinkedList (LinkedList):
    def __init__(self):
        self.head = self.tail = None
        self.count = 0
        
    def prepend(self, value):
        pass
        
    def append(self, value):
        pass
In [93]:
class LinkedList (LinkedList):
    def __init__(self):
        self.head = self.tail = None
        self.count = 0
        
    def prepend(self, value):    
        self.head = LinkedList.Node(value, next=self.head)
        if self.tail is None: #if the list was previously empty
            self.tail = self.head
        self.count += 1
        
    def append(self, value):
        if not self.head:
            self.prepend(value)
            
        else: #gurantee that the list is not empty
            self.tail.next = LinkedList.Node(value)
            self.tail = self.tail.next
            
            #self.tail.next = self.tail = LinkedList.Node(value) #also working
            
            self.count += 1
In [94]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst
Out[94]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [95]:
len(lst)
Out[95]:
10

3. Implementing deletion

Deleting the head

In [96]:
class LinkedList (LinkedList):
    def del_head(self):
        assert(len(self) > 0)
        self.head = self.head.next
        if self.head is None: #removed the last element
            self.tail = None
        
        self.count -= 1
In [97]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
    
lst.del_head()
lst.del_head()

lst
Out[97]:
[2, 3, 4, 5, 6, 7, 8, 9]
In [98]:
lst.del_head()
lst
Out[98]:
[3, 4, 5, 6, 7, 8, 9]

Deleting the tail

In [99]:
class LinkedList (LinkedList):
    def del_tail(self):
        assert(len(self) > 0)
        
        if self.head is self.tail:
            self.del_head()
        
        else:
            n = self.head
            while n.next is not self.tail:
                n = n.next # n refers to the node just before the tail

            self.tail = n
            self.tail.next = None

            self.count -= 1
In [100]:
lst = LinkedList()

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

lst.del_tail()
lst.del_tail()
lst
Out[100]:
[0, 1, 2, 3, 4, 5, 6, 7]
In [ ]:
lst.del_tail()
lst
In [103]:
class LinkedList:
    class Node:
        def __init__(self, val, prior=None, next=None):
            self.val = val
            self.prior = prior
            self.next  = next
    
    def __init__(self):
        self.count = 0
        self.head = LinkedList.Node(val = None) #sentinel node (data-less)
        self.head.next = self.head.prior = self.head
        
    def prepend(self, value):
        n = LinkedList.Node(value, prior = self.head, next = self.head.next)
        
        self.head.next.prior = n
        self.head.next = n
        
        self.count += 1
        
    def append(self, value):
        n = LinkedList.Node(value, prior = self.head.prior, next = self.head)
        
        #self.head.prior.next = n
        #self.head.prior = n
        self.head.prior.next =  self.head.prior = n
        
        self.count += 1
        
    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) + ']'
In [63]:
class LinkedList:
    class Node:
        def __init__(self, val, prior=None, next=None):
            self.val = val
            self.prior = prior
            self.next  = next
    
    def __init__(self):
        self.head = LinkedList.Node(val=None) #sentinel (data-less) node
        self.head.next = self.head.prior = self.head
        self.count = 0
        
    def prepend(self, value):
        n = LinkedList.Node(value, prior=self.head, next=self.head.next)
        self.head.next.prior = n
        self.head.next = n
        self.count += 1
        
    def append(self, value):
        n = LinkedList.Node(value, prior = self.head.prior, next=self.head)
        self.head.prior.next = n
        self.head.prior = n
        
        self.count += 1


    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) + ']'
In [104]:
lst = LinkedList()
for i in range(10):
    lst.prepend(i)
for i in range(10):
    lst.append(i)
lst
Out[104]:
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

5. 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)$