< Back

Lecture 26 - Linked Lists

---

As usual, create a directory to hold today's activities:

  $ mkdir ~/cs170/labs/lab26 
  $ cd ~/cs170/labs/lab26 

---

Data Structures

We saw the very simple form of creating linked lists last class, but there were still some lingering questions: Where are these nodes being stored? Why do we need this internal class? Where do these objects exist and go during run time? etc. Today, I want to clear that up a little bit, as well as introduce how we can remove things from the linked list. And finally stop having to manually compile everything every time.

---

• LinkedList.h
• LinkedList.cc
• LinkedDriver.cc
• Makefile

Another nice thing about python lists is that we can insert data into arbitrary locations within the list. However, right now we can only add to the front of the linked list. We should definitely add a mechanism to add to arbitrary locations in the linked list.

Another operation we have used a lot for python lists is "remove". Remove takes a value from the list, and removes the first instance of that value. Removing elements from a linked list is interesting, because we essentially just have to re-order the list so that the node we removed is skipped over when we traverse over the list.

Details

You will need to write two new methods for your LinkedList class: insert and deleteNode.

insert takes two parameters: the first is the data that you want to add to the list, and the second is the location in the list that you want to add that element. This method will create a new node, and rearrange the references to include that node in the correct location of the linked list.

deleteNode takes one parameter: the data that the node you want to delete contains. This method will find the first node that contains the specified data, and removes it from the list.

Make sure you test your methods carefully. Think about what the edge cases are, and how to handle them appropriately.

Example

  #define SIZE 10
  LinkedList list;

  for(int i = 1; i <= SIZE; i++) {
     list.append(i);
  }

  cout << list << endl;
  //[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]		  

  list.insert(0, 1)
  cout << list << endl;
  //[1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10]

  list.delete(8);
  cout << list << endl;
  //[1, 0, 2, 3, 4, 5, 6, 7, 9, 10]

Hint

 

---