Search this site

List Implementation Followup

LinkedList: Insert

Allow the user to insert an item in the ith spot, e.g.

         linkedList.insert(3,"Bob")

This call would put "Bob" after the 2nd Element in the list.

How would you implement Insert for a LinkedList?

First, let's draw some pictures. You need to traverse to the right spot, then fix two links:







Now, let's look at the code:

        class LinkedList:
            def __init__(self):
                self.head=None
                self.tail=None

            # ...
            def insert(self,i,x):
            # instructor will demo this...



ArrayList:Insert

Draw some pictures:


Big-O Analysis





In-Class Assignment

Add insert and remove to your LinkedList class.

Recent site activity