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.