Linked Lists - Lists

From TRCCompSci - AQA Computer Science
Jump to: navigation, search

Linked List

A linked list is a list where each value is aware of the data that comes before and after the value.

This is achieved by each node having a data value to store the data and a pointer value to point to the next item in the list. We will also need to have a pointer to identify the start of the list.

Linked list.png

To add an item into the linked list:

  • you can put the new data into a current space
  • find the value it needs to go after and copy the pointer value
  • set this pointer value so it points to the new item
  • set the pointer of the new value to the copied pointer value

To delete an item from the linked list:

  • Find the item you wish to delete
  • Copy the pointer value of this item
  • Find the item which points to the item to delete
  • Replace the pointer value of this item to the copied value

Expanded Version

You could have two lists, one is a list of the available spaces within the structure, and the other is the actual list of values to store.

This way you will know the first available space without the need to search for it. Two pointers are need for the list, one for the start of the list and one for the start of the free spaces.