Chapter 35 - Lists And Linked lists Flashcards
State an advantage of using linked lists
The data can be sorted In different ways without making any changes to the original data.
How can data be ordered and maintained?
It is possible to maintain an ordered collection of data items using and array, which is a static data structure
How is a linked list initialised?
The array is initialised before entering any data.
After initialisation a pointer named start will point to the first data item in the list.
This will be initialised to null indicating that the list is empty.
What happens when a new item is added to the list
Data is stored at the location indicated by the free storage pointer
Alter the free storage pointer to the next free storage space
Identify where in the list it is to be inserted
Set the pointer for the item that will precede it to the new data item
Update the pointer for the new data item to that previously stored in the item that preceded it
To delete data from the list
Follow the pointers until data item to delete is found
Change the previous nodes pointer to point to the node pointer to by the item that is being deleted
Change data item being deleted to point to nextfree
Change nextfree to point to node being deleted
Note
Data isn’t physically removed from the structure, instead the pointer is used to say the item can be overwritten
what is a linked list?
A data structure that provides a foundation where other structures can be built.
e.g. stacks, queues, graphs and trees
describe the structure of a linked list
A linked list is constructed from nodes and pointers
what identifies the first node?
A start pointer identifies the first node
what does every node contain in a linked list?
each node contains data and a pointer to the next node
state one advantage of using linked lists
data in lists can be stored anywhere in memory, with pointers indicating the address of the next item
how can a circular linked list be created?
A circular linked list can be created by making the last node point to the first node
how can a doubly linked list be created?
by adding an extra pointer, nodes can point to the previous and next items, known as a doubly linked list
what is a doubly linked list?
a list containing 2 pointers with nodes that can point to previous and next items
