Chapter - 35 Lists and linked lists

Question 1

What is a list?

Answer 1

» Ordered data structure
» Dynamic
» Accessing the data involves using an index

Question 2

What is the operation to test an empty list?

Answer 2

» isEmpty()

Question 3

What is the operation to add a new item to list to the end of the list?

Answer 3

» Append(item)

Question 4

What operation is used to remove the first occurrence of an item from the list?

Answer 4

» remove(item)

Question 5

What operation is used to search for an item in a list?

Answer 5

» search(item)

Question 6

What operation can you use to return the number of items in a list?

Answer 6

» length()

Question 7

What operation can return the position of an item?

Answer 7

» index(item)

Question 8

What operation can insert a new item at a position number?

Answer 8

» insert(pos,item)

Question 9

What operation can remove and return the last item in the list?

Answer 9

» pop()

Question 10

What operation can remove and return the item at a position number?

Answer 10

» pop(pos)

Question 11

What is the difference between an array and a list?

Answer 11

» List is dynamic
» Array is static

Question 12

How do you insert a new name in the list?

Answer 12

» 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

Question 13

How do you delete a name from the list?

Answer 13

» 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

Question 14

What is a linked list?

Answer 14

» Dynamic data structure used to hold an sequence
» It provides a foundation upon which other structures can be built

Question 15

What are some features of a linked list?

Answer 15

» Items which form the sequence are not necessarily held in contiguous data locations, or in the order in which they occur in the sequence

Question 16

What is each item in the linked list called?

Answer 16

» A Node
» Contains a data field and a next address field called a link or pointer field

Question 17

What does the data field contain?

Answer 17

» Actual data associated with the list item

Question 18

What does the pointer field contain?

Answer 18

» The address of the next item in the sequence

Question 19

What is the use of the null pointer?

Answer 19

» The link field in the last item indicates that are no further items by the use of a null pointer

Question 20

What is the start pointer?

Answer 20

» Identifies the first node in the list

Question 21

How do we initialize a linked list?

Answer 21

» Keep two linked lists
» One for the actual data
» One for the free space

Question 22

What does the start pointer aim to in a new initalised linked list?

Answer 22

» First item in the list, initialised to null

Question 23

What does null indicate?

Answer 23

» A list is empty

Question 24

Which pointer does the last item of an empty list have?

Answer 24

» Pointer of null

Question 25

What does the pointer point to?

Answer 25

» To the next index

Question 26

What is the nextfree pointer?

Answer 26

» Points to the next free location in the array

Question 27

What does Names[p].name do?

Answer 27

» Holds the name in node[p]

Question 28

What does Names[p].pointer do?

Answer 28

» Holds the value of the pointer in node [p]

Question 29

What are the steps to insert a new item to a linked list?

Answer 29

» 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

Question 30

How can you traverse a linked list?

Answer 30

» 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

Question 31

Define the meaning of traverse

Answer 31

» Processing of where you access each element and every element present in a data structure

Question 32

How can you make a circular linked list?

Answer 32

» 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

Question 33

What is the advantages of implimenting a linked list using object oriented techniques?

Answer 33

» 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

Question 34

What are the uses of a linked list?

Answer 34

» Operating system manages a processor to store processor to store process blocks in a ready state » Music players to store tracks in a platlist

Question 35

What happens if the linked list is empty when a node is being added to it?

Answer 35

» New node becomes the first item » Creates a start pointer to it

Question 36

What happens if the new node should be placed before the first node?

Answer 36

» New node becomes the first node - Change the start pointer to it » New node points to the second node

Question 37

What are the steps if the new node is to be placed inside the linked list?

Answer 37

» 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

Question 38

How do we delete items from a linked list?

Answer 38

» 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

Question 39

What happens if the item to delete is in the linked list?

Answer 39

» 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