Suppose we have n data values stored in a file and a program reads these values into an ordered collection implemented using the vector technique discussed in the previous lesson. Suppose also that, as a value is read in from the file, it is inserted at the beginning of the ordered collection; that is, the addFirst operation is called. Determine, using big-O notation, the running time for this program assuming that the file contains n data values.
Are there occasions for which we should still want to use a vector or an ordered collection implemented with a vector to receive file input, despite the problems we have discussed in this section? If so, discuss the reasons why.
Describe the case that causes the least amount of work during a data movement process in an ordered collection that is implemented with a vector. Does this occur during the insertion or removal, and where?
Suppose you sort a list of input values by reading them in one at a time and inserting them into a sorted collection object in the previous lesson. Clearly, after you have read all of the input values, you will have a sorted list. Let's call this technique the sorted collection sort algorithm. Using big-O notation, analyze the time efficiency of this algorithm in terms of number of comparisons and number of data interchanges. Be sure that you take into account the underlying implementation strategy that we used for the sorted collection. Compare the efficiency of this algorithm to the efficiencies of the other sort algorithms we have studied -- insertion, bubble, selection, and radix sort.
Based on the operations for a linked list discussed, describe how the linked list ADT differs from the ordered collection ADT.
Describe two applications for which a linked list is a suitable data structure.
Explain why so many linked list operations assume that the atEnd operation returns false.
Draw a picture of a linked list with three nodes. The current pointer should be aimed at the first node. Now draw pictures that show each step during the process of removing this node from the list.
Suppose that the length of a linked list is not maintained as a spearate component of the data structure. How does this change affect the behavior of the length operation?
Describe the method used by a new linked list operation called insertLast. This operation expects a data element as a parameter and inserts it at the end of a linked list. The only precondition is that the list is initialized. Categorize the efficiency of this operation using big-O notation.
Describe how to overload the assignment operation for vectors so that one can assign the contents in successive nodes of a linked list to the successive indices of a vector. Why would this operation be useful?
Overload the + operator to define a C++ function that concatenates two linked lists and returns the result. Categorize the efficiency of this operation using big-O notation.
Given a linked list of ints, write a loop that starts at the beginning of the linked list and returns the position of the first list node with the value 0 in its data field. If no such node exists in the list, -1 should be returned.
Write a function sum to sum the integers in a linked list of integers.
Write a function to remove all of the nodes in a linked list.
Write a function called merge that receives two linked lists of integers arranged in ascending order. Your function should merge these two lists into a single list, also arranged in ascending order. The merged list should be returned from the function.
Implement the remaining linked list member functions.
For each linked list member function implemented in this section and in Exercise 1, provide a big-O efficiency analysis.
State an algorithm for an addFirst operation for linked lists and write the corresponding C++ member function. Then provide a big-O analysis for your implementation of this operation.
State an algorithm for an addLast operation for linked lists and write the corresponding C++ member function. Then provide a big-O analysis for your implementation of this operation.
Compare the efficiencies of addFirst and addLast. Which is more expensive to run and why?
State an algorithm and write a function for an index operation that allows access and modification of a data value at a given position in a linked list. Overload the operator [ ] for the function. After you've written the function, provide a big-O analysis of its efficiency.
Describe the differences between the index operation defined in Exercise 6 for linked lists and the index operation for vectors.
Suppose we drop the mySize data member from the definition of a linked list. Rewrite the function length so that it still returns the number of nodes in a list. What was the efficiency of length in the originial implementation? What is the efficiency of the new implementation?
Discuss the difference between an address and the value stored at that address.
Draw pictures of the computer's memory, with binary addresses and data values, that show the memory cells for the following statements.
a. int x = 2, y = 3, z = 4;
b. double a = 4.8, b = 7.6;
c. char ch = 'a';
d. double list[5];
e. double * realPtr = 0;
f. struct
{
int first;
double second;
} aStruct;
Write a program to test for how many nodes can be allocated for a linked list of integers until the heap has no more memory. You can accomplish this by writing a count-controlled loop whose upper bound is an input integer and which adds a new data element to the beginning of the list on each pass. Start with the input of a large integer, and if an error occurs, try another integer of half that size. If an error does not occur, repeat the input with an integer half again the size of the previous input. When your inputs alternate between an integer that causes an error and an integer that is 1 less that does not cause an error, you will have determined how many nodes can be obtained for storing integers from the heap.
Simon Seeplus recommends that we use a linked list rather than a vector to implement the data member of the ordered collection class. He argues that the ordered collection class will then solve the data movement and the file input problems very efficiently. Discuss his proposal. Does it violate any of the requirements of the ordered collection class?
Refer to the following data declaration:
struct node
{
int data;
node * next;
};
node * a;
node * b;
node * c;
Specify which of the following statements are syntactically correct.
For those that are wrong, explain why they are wrong.
a. a = b;
b. a = a->data;
c. a = a->nodeptr;
d. delete a;
e. delete b->data;
f. delete b;
Refer to the following data declaration:
struct node
{
int data;
node * next;
};
node * a;
node * b;
node * c;
Show how the schematic below would be changed by each of the following:
a. a = a->next;
b. b = a;
c. c = a->next;
d. b->data = c->data;
e. a->data = b->next->data;
f. c->next = a;
Refer to the following data declaration:
struct node
{
int data;
node * next;
};
node * a;
node * b;
node * c;
Write one statement to change
to
Refer to the following data declaration:
struct node
{
int data;
node * next;
};
node * a;
node * b;
node * c;
Consider the following list:
Write code to create a new linked list element with value 12 and insert it at the beginning of the list headed by a.
Refer to the following data declaration:
struct node
{
int data;
node * next;
};
node * a;
node * b;
node * c;
Consider the following list:
Write code to remove the element at the head of the list and then add this element at the end of the list.
Refer to the following data declaration:
struct node
{
int data;
node * next;
};
node * a;
node * b;
node * c;
Indicate the output for each of the following:
a. a = new node;
b = new node;
a->data = 10;
b->data = 20;
b = a;
a-> data = 5;
cout << a->data << " " << b->data << endl;
b. c = new node;
c->data = 100;
b = new node;
b->data = c->data % 8;
a = new node;
a->data = b->data + c->data;
cout << a->data << " " << b0->data << " " << c->data << endl;
c. a = new node;
b = new node;
a->data = 10;
a->next = b;
a->next->data = 100;
cout << a->data << " " << b->data << endl;
Use for 11, 12, 13. Assume that the member names of a node are data and next and that the external pointers first, probe, and trailer and the integer variable number have been declared and initialized as follows:
For the following statements labeled a through e, draw a picture of the
state of these objects after the statements have been executed. Assume
that the state of the objects carries over from one exercise to the
next.
a.
probe = first;
trailer = first;
b.
while (probe != 0)
{
trailer = probe;
probe = probe->next;
}
c.
number = trailer->data;
d.
delete probe;
e.
trailer->next = 0;
Suppose that someone forgot to declare and implement a destructor for the linked list class. Describe a situation in which this omission is likely to cause problems.
Assume that the member names of a node are data and next and that the external pointers first, probe, and trailer and the integer variable number have been declared and initialized as follows:
Suppose that a bug has been introduced into the linked list
implementation so that linked lists of the following form are created:
(insert here)
Describe the problems that this structure would cause for a sequential search for a given data element in the list.
Do a big-O analysis of each of the operations for a one-key table assuming the linked list implementation strategy is used.
Just as we have used a linked list instead of a vector to implement a one-key table, we can also use a linked list to implement an ordered collection. Assuming such an implementation, do a big-O analysis of each of the operations for an ordered collection.
Just as we have used a linked list instead of a vector to implement a one-key table, we can also use a linked list to implement an ordered collection. Assuming such an implementation, do a big-O analysis of each of the operations for a sorted collection.
We described an implementation of the two-key table ADT that was layered on one-key tables. Assuming a linked list implementation of the one-key tables on which the two-key table is layered, provide a big-O efficiency analysis of each of the operations for the two-key table.
Add merge and append operations to the interface of one-key table and implement the operations. You may rely on the corresponding list operations developed earlier.