Linked lists

A linked list data structure is designed using object-oriented programming.

The design includes two classes called node and linkedList.

Describe the features of a linked list data structure.

The class design for node is shown here.

new() is the constructor method. The constructor method takes a parameter and assigns this to the value attribute.

The method getNextNode() returns the attribute nextNode.

Write the method getNextNode() using pseudocode or program code.

The method setValue() takes an integer as a parameter and assigns this to the attribute value

Write the method setValue() using pseudocode or program code.

The class design for linkedList is shown here.

new() is the constructor method. The constructor initialises the attribute headNode to a null value.

Write the constructor method using pseudocode or program code.

The class design for node and linkedList are shown again here for your reference.

The method getValue() will return the value of a node. The method getNextNode() will return the next node to be accessed in the linked list.

The method outputList() traverses the linked list starting at the node headNode. The method joins the data in each node and returns it.

Complete the method outputList() using pseudocode or program code.

The method insertNode() will insert a new node into the linked list.

The method accepts an integer as a parameter, creates a new node with that data and inserts it into the linked list, e.g. insertNode(8) creates a node object with the data 8 and adds it to the linked list.

The program needs to store the following data items in the linked list in the order they are given: 10 25 39

The program then needs to output all of the data in the list using the appropriate method.

Write an algorithm using pseudocode or program code to:

• create a new linkedList object with the identifier createList

• insert each of the data items into the linked list (10, 25, 39)

• output the content of the linked list.

A new method is needed to remove a node from the linked list. The method needs to take the data to remove as a parameter and then find this data in the linked list before removing the node.

Describe the steps that this method will need to follow and the decisions that need to be made in the method to remove the correct node.

The program developer made use of computational methods when designing the object-oriented programming solution. One computational method is divide-and-conquer.

Identify three other computational methods that the program developer could have used.

* This program uses classes and objects to create a linked list.

An alternative method is creating a 2-dimensional array. In this design the first index stores the data and the second element stores the index of the next data item. Array elements not currently used are also linked together to form a chain of empty values to identify where the next data item can be inserted.

Compare the two different methods of creating a linked list that have been described.

You should include the following in your answer:

• the features of both methods including the reusability of program components

• benefits and drawbacks of both methods in this program

• a conclusion evaluating the efficiency of both methods when designing a program that needs

a linked list.

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user.

The action the algorithm takes depends on the value input by the user. These actions are listed in

Complete the pseudocode here to implement Sundip’s algorithm.

Complete the following table to give the output from this algorithm when the following set of inputs are entered by the user. The letters will complete an action stated in Fig. 2

If the user enters 4 2 S A E, the algorithm will not work correctly.

Explain what problem this input data will cause and why the problem occurs.

A stack is one data structure that is available for Sundip to use. She could also use a queue, list, linked list, array or tuple.

Describe one difference between a stack and a queue.

Describe one difference between an array and a list.

State how a tuple is different to a list.

Describe how the second item in a linked list would be accessed using pointer values.

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

State the purpose of headPointer and freeListPointer in the linked list shown in Fig. 3.

State the meaning of the pointers with the value NULL in the linked list shown in Fig. 3.

A procedure outputs the data in the linked list shown in Fig. 3 from the first item in the list, to the last item.

Give the output from the procedure.

A new item needs to be added to the linked list.

Describe how a new item is added to a linked list.

The function findNode will search the linked list and return either the position of the node that contains the data item, or-1 if the data item is not found.

The data held in a node at location x can be accessed with linkedList[x].data. The pointer of the node at location x can be accessed with linkedList[x].pointer.

Complete the function, using pseudocode or program code.

A business uses an array with the identifier wNames to store workers’ names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed.

State the name of the type of data structure described above.

Using pseudocode, write an algorithm that allows the user to enter a name which is then pushed onto the data structure above, checking first that the data structure is not full.

The same workers’ names are stored in a binary search tree which is ordered alphabetically.

Kirstie is set as the root node, with Martyn, Louise, Alex and Anna added one by one.

Complete the tree diagram above to show where Martyn, Louise, Alex and Anna would

be added to this binary search tree.

Describe the process of using the binary search tree above to search for the name “Zoe”.

Compare the efficiency of a binary search tree to a linked list when searching for data.

Compare the efficiency of a binary search tree to a hash table when searching for data.

An object oriented system is implemented to organise further information about each worker’s attendance. Classes, objects, methods and attributes are used in this system.

State the meaning of each of the following terms:

Object........

Method........

Attribute........

Each worker has a name and an attendance figure which can be between 0 and 100.

Write a definition for a fully encapsulated customer class, providing both get and set methods for all attributes. You do not have to write code for the constructor method.

Barney is writing a program to store data in a linked list. He is writing the initial program for a maximum of 10 data items.

Each node in the linked list has a data value and a pointer (to the next item).

A null pointer is stored with the value –1.

Describe the purpose of freeListPointer.

State the purpose of headPointer.

Barney wants the nodes to be stored as objects using object-oriented programming. He designs the following class.

The constructor assigns the parameters to the attributes to create an object.

The class node, uses get methods and set methods.

Describe one difference between get methods and set methods.

The function findNodePath() takes the data item to find in the linked list as a parameter and follows the pointers to find the required node.

The function returns the array indexes of all the nodes it visits and joins this to a suitable message stating whether the data was found or not found and then returns this as one string.

Describe how the function findNodePath() will search for the data item and return the required message.

The procedure printLinkedList() follows the pointers to print all of the elements in the linked list.

The procedure has a number of errors.

Identify the line of each error and write the corrected line.

Error 1 line number........

Error 1 correction........

Error 2 line number........

Error 2 correction........

Error 3 line number........

Error 3 correction........

Barney will use an Integrated Development Environment (IDE) to debug his program code.

Describe three features commonly found in IDEs that Barney could use to debug his program code.

* Barney would like his linked list to be part of a base program that is saved in a library. This means that it can be reused and changed by other programs.

Discuss the benefits of using different object-oriented techniques that Barney could use to achieve this.

A programmer is writing software for a firewall. She is writing code so that it keeps a track of websites that users are permitted to visit. The software stores the websites’ addresses along with details about who can view them and when.

The following data is also stored about each website:

• Access level needed (1-4) • If it is available all the time (true) or just lunch times and out of work hours (false).

So a website which is available to users of access level 2 and above, all the time, would have the details [2, true] stored.

A website accessible to users of access level 3 and above, only outside of work hours, would have the details [3, false] stored.

State the name of a data structure that could be used to store a single site’s details.

A flaw with the current hash function is it tends to generate lots of collisions (addresses that compute to the same hash). Below is a diagram of part of the hash table. The address www.rnd.com with details [2, true] is being added to the hash table.

Explain how a hash table can be used to handle collisions, referring to the example below.

The hash function is changed so there are no longer high numbers of collisions.

During busy periods the firewall is expected to check several addresses a second. It is anticipated that roughly 10 new addresses will be added to a whitelist (list of acceptable addresses) each day.

There is a debate as to whether a hash table (with the new hash function) is the best approach, or if the whitelist would be better stored in a linked list.

*Discuss whether a hash table or linked list is better to store acceptable websites. You should compare how each structure can be searched and has data added and come to a

recommendation as to which is better for the whitelist.

A program needs to store the names of plants that are in a garden, so they can be easily found and accessed in alphabetical order.

The data is stored in a tree structure. Part of the tree is shown.

State the type of tree shown in Fig. 2.1.

Show the output of a breadth-first traversal of the tree shown in Fig. 2.1.

Explain how backtracking is used in a depth-first (post-order) traversal. Use the tree in Fig. 2.1 in your explanation.

The elements in the tree in Fig. 2.1 are read into a linked list producing an alphabetised list.

Complete the following table to show the linked list for the data.

A new plant, Lavender, needs adding to the linked list. The linked list needs to retain its alphabetical order.

Complete the table to show the linked list after Lavender is added.

Hosta needs removing from the linked list.

Explain how a data item is removed from a linked list. Use the removal of Hosta in your answer.

The linked list is stored as a 2D array with the identifier plantList. The index of the first element of the linked list is stored in the identifier firstElement.

All contents of the linked list need to be output in alphabetical order.

Write an algorithm to follow the pointers to output the contents of the linked list in alphabetical order.

Add comments to explain your code.

A coach company offers tours of the UK.

A linked list stores the names of cities on a coach tour in the order they are visited.

Describe what is meant by the term ‘linked list’.

The tour is amended. The new itinerary is: London, Oxford, Manchester then York. Explain how Birmingham is removed from the linked list and how York is added. You may use the diagram below to illustrate your answer.

The program stores records about its customers.

Often an individual customer’s record needs to be accessed. This is done by searching using the Customer ID. Explain why a hash table is better suited than a linked list to store the customer records, particularly as the company acquires more customers.

A programmer is developing an ordering system for a fast food restaurant. When a member of staff inputs an order, it is added to a linked list for completion by the chefs.

Explain why a linked list is being used for the ordering system.

Order 158 has been made, and needs adding to the end of the linked list.

Add the order, 158, to the linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

Order 159 has been made. This order has a high priority and needs to be the second order in the linked list. Add the order, 159, to the original linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

The linked list is implemented using a 2D array, theOrders:

• Row 0 stores orderNo

• Row 1 stores next

The data now stored in theOrders is shown in Fig. 2.2.

The following algorithm is written:

Outline why nodeNo does not need to be stored in the array.

Complete the trace table for procedure x, for the data shown in Fig. 2.2.

Describe the purpose of procedure x.

A new order, 190, is to be added to theOrders. It needs to be the third element in the list. The current contents of the array are repeated here for reference:

Describe how the new order, 190, can be added to the array, so the linked list is read in the correct order, without rearranging the array elements.

The user needs to be able to search for, and find, a specific order number.

State an appropriate search algorithm that could be used, and justify your choice against an alternative Search algorithm.

Appropriate Search Algorithm........

The programmer is writing the program using an IDE.

Identify three features of an IDE that the programmer would use when writing the code and describe how the features benefit the programmer.

(f*) The programmer is considering using concurrent programming.

Discuss how concurrent programming can be applied to the food ordering system and the

benefits and limitations of doing so.