Computer Science
Linked Lists

A linked list is a dynamic data structure to hold data in sequence.

  • Items are not necessarily stored in contiguous (next to each other) data locations.
  • Items in a linked list are called nodes. Nodes contain a data field and a pointer to the address of the next item.
  • The data field holds the actual value of the list item, the pointer field contains the address of the next item.
  • The pointer field of the last item indicates this using a special value (eg 0 or -1).
  • In addition, a pointer variable must be stored showing the address of the first item in the list.
  • It is also common to store the location of the next free address.

The term, Dynamic Data Structure refers to the fact the memory needed to store a linked list will vary at runtime.

Linked List Simulation

 







Linked List Algorithms

Implementing a linked list with an array, requires an array of records. In the example, there are 2 fields in the record, the name and the pointer. You need global variables to store the following,

  • Maximum List Size
  • Start Address
  • Next Free Address

To Insert An Item

This algorithm is long because there are 3 scenarios to consider. The item might be placed as the first item in an empty list, it might be the first item in the list or it might be placed at some other location in the list.

Get New Item Name
If nextfree = 0 then
   Prompt user list is full
   Exit Sub
End If
Set item[nextfree].name to new item name
If start = 0 (list currently empty) then
   item[nextfree].pointer = 0
   nextfree = 2
   start = 1
   Exit Sub
End If
Ptr = start
If newItem<item[Ptr].name (at front of list) Then
   tempPtr = item[nextfree].pointer
   item[nextfree].pointer = start
   start = nextfree
   nextfree = tempPtr
Else (place within list)
   placed = false
   While Placed Is False And item[Ptr].pointer <> 0
      If newItem>=item[item[Ptr].pointer].name Then
         Ptr = item[Ptr].pointer
      Else
         placed = true
      End If
   End While
   tempPtr = nextfree
   nextfree = item[nextfree].pointer
   item[tempPtr].pointer = item[Ptr].pointer
   item[Ptr].pointer = tempPtr
End If

To Find The Previous Item In The List

In order to process deletions from the list, it will be necessary to work out which item points to the item to be deleted.

tempP= start
Do
   previous = tempP
   tempP = item[tempP].pointer
Loop While tempP <> Address Of Item To Delete
Return previous

To Delete An Item

itm = Address Of Item To Delete
If Empty List Then
   Prompt User
   Exit Sub
End If
If item[itm] = start (first in list) Then
   tempPtr = item[itm].pointer
   item[itm].pointer = nextfree
   start = tempPtr
   nextfree = itm
   Exit Sub
End If
If item[itm].pointer = 0 (last in list) Then
   item[itm].pointer = nextfree
   nextfree = itm
   item[findPrevious(itm)].pointer = 0
   Exit Sub
End If
(Deal With Other Scenarios)
item[findPrevious(itm)].pointer = item[itm].pointer
item[itm].pointer = nextfree
nextfree = itm

To Output The List In Order

If start = 0 (empty list) Then
   Prompt User
   Exit Sub
End If
startPrint = start
Do
   output item[startPrint].name
   startPrint = item[startPrint].pointer
Loop While startPrint <> 0

Key Terms

A Static Data Structure is a data structure whose size is declared when the program is run. An array is an example of this. If too many locations are set aside for storage, memory is wasted. If too few are set aside the program will not work.

In dynamic data structures, you do not have to reserve memory space. The space used for dealing with dynamic data structures is called the heap. The heap is a pool of available memory locations which can be allocated in blocks to the dynamic structure. When no longer needed, the locations are returned to the heap for use by other applications.

Pointer variables point to memory addresses.

Other Things To Consider

The example list above is obviously far smaller than may be used in practice. In order to store data that needs to be sorted in more than one way, you would need to store additional pointers that sustain this order.

When drawing diagrams of linked lists, you must make sure that you indicate the start and next free addresses. It is also vital that the pointer of the last item is 0 or -1 to indicate the end of the list.