Chapter - 35 Lists and linked lists Flashcards
What is a list?
» Ordered data structure
» Dynamic
» Accessing the data involves using an index
What is the operation to test an empty list?
» isEmpty()
What is the operation to add a new item to list to the end of the list?
» Append(item)
What operation is used to remove the first occurrence of an item from the list?
» remove(item)
What operation is used to search for an item in a list?
» search(item)
What operation can you use to return the number of items in a list?
» length()
What operation can return the position of an item?
» index(item)
What operation can insert a new item at a position number?
» insert(pos,item)
What operation can remove and return the last item in the list?
» pop()
What operation can remove and return the item at a position number?
» pop(pos)
What is the difference between an array and a list?
» List is dynamic
» Array is static
How do you insert a new name in the list?
» Test whether the list is already full, print message if it is and quit
» Determine where new item needs to be inserted
» Starting at the end of the list, move other items along one piece
» Insert new item in correct place
How do you delete a name from the list?
» First delete the name
» Names coming after deleted item need to me moved up to fill the empty space - by copying them to the previous spot in the array
» Finally the last element which is now duplicated is replaced with a blank
What is a linked list?
» Dynamic data structure used to hold an sequence
» It provides a foundation upon which other structures can be built
What are some features of a linked list?
» Items which form the sequence are not necessarily held in contiguous data locations, or in the order in which they occur in the sequence
What is each item in the linked list called?
» A Node
» Contains a data field and a next address field called a link or pointer field
What does the data field contain?
» Actual data associated with the list item
What does the pointer field contain?
» The address of the next item in the sequence
What is the use of the null pointer?
» The link field in the last item indicates that are no further items by the use of a null pointer
What is the start pointer?
» Identifies the first node in the list
How do we initialize a linked list?
» Keep two linked lists
» One for the actual data
» One for the free space
What does the start pointer aim to in a new initalised linked list?
» First item in the list, initialised to null
What does null indicate?
» A list is empty
Which pointer does the last item of an empty list have?
» Pointer of null
What does the pointer point to?
» To the next index
What is the nextfree pointer?
» Points to the next free location in the array
What does Names[p].name do?
» Holds the name in node[p]
What does Names[p].pointer do?
» Holds the value of the pointer in node [p]
What are the steps to insert a new item to a linked list?
» Check if there is free memory for a node, output an error if there is not
» Create a new node and insert data in the node indicated by the free storage pointer
How can you traverse a linked list?
» Check if the linked list is empty
» Start at the node the start pointer is pointing to
» Output the item
» Follow the pointer to the next node
» Repeated until the end is reached
Define the meaning of traverse
» Processing of where you access each element and every element present in a data structure
How can you make a circular linked list?
» By making the last node point to the first node
» Each node in a circular linked list can also have an additional pointer pointing to the previous item - creating a doubly circular linked list
What is the advantages of implimenting a linked list using object oriented techniques?
» Any available memory adress can be used to store data
» Does not need to be adjacent - as each node points to the next in the structure
» Memory footprint of the data structure is not determined at compile time and can change dynamically at run time - Dynamic
What are the uses of a linked list?
» Operating system manages a processor to store processor to store process blocks in a ready state
» Music players to store tracks in a platlist
What happens if the linked list is empty when a node is being added to it?
» New node becomes the first item
» Creates a start pointer to it
What happens if the new node should be placed before the first node?
» New node becomes the first node - Change the start pointer to it
» New node points to the second node
What are the steps if the new node is to be placed inside the linked list?
» Start at the first node
» If the data in the current node is less than the value of the node, follow the pointer to the next node until position is found
» New node is set to point where the previous node pointed
» Previous nodes set to point to the new node
How do we delete items from a linked list?
» Check if the linked list is empty and output an error if there is no start node
» If the first item is the item to delete, set the start pointer to the next node
What happens if the item to delete is in the linked list?
» Find the node to delete
» Previous node’s pointer is set to the next node after the delete one
» Follow the new nodes pointer to the next node
» Update the free pointers
