Linked Lists

Agenda

  1. The LinkedList and Node classes
  2. Implementing append
  3. Implementing deletion
  4. Bidirectional links (Doubly-linked list) & Sentinel head
  5. Incorporating a "cursor"
  6. Run-time analysis

1. The LinkedList and Node classes

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

2. Implementing append

Option 1

In [3]:
class LinkedList (LinkedList): # note: using inheritance to extend prior definition
    def append(self, value): #O(N)
        
        if len(self) == 0: #self.head is None  or self.count == 0
            self.prepend(value)
        else:
            n = self.head
            while n.next:
                n = n.next
            #now n refers to the last element in the linkedlist
        
            n.next = LinkedList.Node(value, next=None)
            self.count += 1
In [4]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst
Out[4]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Option 2

In [5]:
class LinkedList (LinkedList):
    def __init__(self):
        self.head = self.tail = None
        self.count = 0
        
    def prepend(self, value): #O(1)
        self.head = LinkedList.Node(value, self.head)
        
        if not self.tail: #if self.tail is None
            self.tail = self.head
        
        self.count += 1
        
    def append(self, value): # O(1)
        
        if len(self) == 0:
            self.prepend(value)
        else:
            #guaranteed that the list is not empty, and the tail is initialized
            self.tail.next = LinkedList.Node(value, next=None)
            self.tail = self.tail.next
            
            #self.tail.next = self.tail = LinkedList.Node(value, next=None)
            
            self.count += 1
In [6]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst
Out[6]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

3. Implementing deletion

Deleting the head

In [7]:
class LinkedList (LinkedList):
    def del_head(self): #O(1)
        assert(len(self) > 0)
        
        if self.head:
            self.head = self.head.next
            self.count -= 1
        
        if len(self) == 0:
            self.tail = None
In [8]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst.del_head()
lst.del_head()
lst
Out[8]:
[2, 3, 4, 5, 6, 7, 8, 9]

Deleting the tail

In [9]:
class LinkedList (LinkedList):
    def del_tail(self): #O(N)
        assert(len(self) > 0)
        
        if len(self) == 1:
            self.head = self.tail = None # or self.del_head()
        else:
            # know there are at least 2 elements 
            n = self.head
            while n.next.next: #n.next is not self.tail 
                n = n.next
                
            # n refers to the node before the tail
            n.next = None
            self.tail = n
            self.count -= 1
In [10]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst.del_tail()
lst.del_tail()
lst
Out[10]:
[0, 1, 2, 3, 4, 5, 6, 7]
In [11]:
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(None)   #create a "sentinel" node
        self.head.prior = self.head
        self.head.next = self.head
        self.count = 0
        
    def prepend(self, value): #O(1)
        n = LinkedList.Node(value, prior=self.head, next=self.head.next)
        self.head.next = n
        self.head.next.prior = n
        self.count += 1
        
    def append(self, value): #O(1)
        
        n = LinkedList.Node(value, prior=self.head.prior, next=self.head)  # creat a new node
        #self.head.prior.next = n 
        #self.head.prior = n
        
        n.prior.next = n
        n.next.prior = n
        
        self.count += 1

    def __getitem__(self, idx): #O(N)
        assert(idx < self.count)
        
        n = self.head.next
        
        for _ in range(idx):
            n = n.next
        
        return n.val
        
    def del_head(self): #O(1)
        assert(len(self)>0)
        
        to_del = self.head.next
        
        to_del.prior.next = to_del.next
        to_del.next.prior = to_del.prior
        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 [12]:
lst = LinkedList()
for i in range(10):
    lst.prepend(i)
lst
Out[12]:
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
In [13]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst
Out[13]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [14]:
lst.del_head()
lst
Out[14]:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
In [15]:
lst[4]
Out[15]:
5

5. Incorporating a "cursor"

In [23]:
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 = self.cursor = LinkedList.Node(None)
        self.head.prior = self.head.next = self.head
        self.count = 0
                
    def append(self, value):
        n = LinkedList.Node(value, prior=self.head.prior, next=self.head)
        n.prior.next = n.next.prior = n
        self.count += 1
        
    def cursor_set(self, idx):
        assert(idx < self.count)
        
        n = self.head.next
        
        for _ in range(idx):
            n = n.next
            
        self.cursor = n
    
    def cursor_get(self, idx):
        return self.cursor.val

    def cursor_insert(self, x): #insert a new node after the cursor
        
        n = LinkedList.Node(x, prior=self.cursor , next=self.cursor.next)
        self.cursor.next.prior = n
        self.cursor.next = n
        self.count += 1
    
    def cursor_delete(self):
        to_del = self.cursor #record the current cursor position
        self.cursor = self.cursor.prior # update the cursor position
        
        to_del.prior.next = to_del.next
        to_del.next.prior = to_del.prior
        
        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 [24]:
lst = LinkedList()
for i in range(10):
    lst.append(i)
lst
Out[24]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [25]:
lst.cursor_set(4)
for x in 'abcd':
    lst.cursor_insert(x)
lst
Out[25]:
[0, 1, 2, 3, 4, d, c, b, a, 5, 6, 7, 8, 9]
In [26]:
lst.cursor_set(8)
for _ in range(4):
    lst.cursor_delete()

lst
Out[26]:
[0, 1, 2, 3, 4, 5, 6, 7, 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)$
In [ ]: