Lists and linked lists

• List


  An abstract data type consisting of a number of items in which the same item may occur more than once, and which is sequenced so that the first, second, third, etc. items can be referred to
• List


  • Very useful data type for a wide variety of operations
  • Can be used to implement other data structures such as a queue, stack or tree
• List of numbers in Python

  • 45, 13, 19, 13, 8
• List operations


  • Test for empty list
  • Append item
  • Remove item
  • Search for item
  • Return length
  • Return index
  • Insert item
  • Pop last item
  • Pop item at position
• Empty


  Return value indicating if the list is empty
• Append item


  Add a new item to the end of the list
• Remove item


  Remove the first occurrence of an item from the list
• Search for item


  Search for an item in the list
• Length


  Return the number of items in the list
• Index


  Return the position of an item in the list
• Insert item


  Insert a new item at a specified position in the list
• Pop last item


  Remove and return the last item in the list
• Pop item at position

  Remove and return the item at a specified position in the list
• Assume that ist names holds the values Jares, Pal, Sepe, Holy
• Adding "Ton" to the list


  names.append("Ton")
• Removing the 4th element from the list


  names.pop(3)
• Inserting "Pal" at index 1


  names.insert(1, "Pal")
• Using an array, it is possible to maintain an ordered collection of data items using an array data structure
• This may be an option if the programming language does not support the linked list data structure
• The maximum number of data items is small, and is known in advance
• The programmer then has to work out and code algorithms for each list operation
• The array must be declared in advance as being a particular length, and this could be for a priority queue
• Inserting a new name in the list

  1. Test for list already full, print message if it is and quit

  2. Determine where new item needs to be inserted

  3. Starting at the end of the list, move other items along a place

  4. Insert new item in correct place
• Deleting the name "Ken" from the list
• The items coming to the list need to be moved up to fill the gap
• List after deleting "Ken"


  • James
  • Holly
  • Nathan
  • Pal
  • Sophie
• Linked list


  A dynamic data structure used to hold an ordered sequence, where the items are not necessarily held in contiguous data locations or in the order in which they occur in the sequence
• Linked list node


  • Contains a data field and a next address field (pointer field)
  • The data field holds the actual data associated with the list item
  • The pointer field contains the address of the next item in the sequence
  • The link field in the last node indicates the end of the list with a null pointer
• Linked list pointer variable


  Points to or contains the address of the first node in the list
• Operations on linked lists

  1. Initialise an empty list

  2. Insert new data in the correct place

  3. Delete an unwanted item

  4. Print out all items in the list

  5. Manage the free space in the list
• Node record definition


  Contains a name field (data field) and a pointer field
• Initialising a linked list

  1. Keep two linked lists: one for the actual data, and one for the free space

  2. When a new node is added, it is put in the node pointed to by nextfree

  3. When a node is deleted, it is linked into the free space list
• The array is initialized prior to entering any names, and it will consist of one ad
• Initialization indicates that the list is empty
• The last item in the free space list has a pointer of a
• A pointer named start will point to the first data item in the list
• The start pointer indicates that he is the last available free space in the list
• The array holding the data list now looks like this: index 0, name 1, pointer 2, 3, 4, 6
• After the names Browning, Turner, Johnson and Cray have been added, the array looks like this: index 0, name Browning, pointer 3, Turner, 4, Johnson, 7-35, Cray, 2, nextfree 4, 4, 6, 5
• We now have two linked lists going, one linking the nodes containing the names, and one linking the free nodes