1. Consider the following conceptual
representation for a linked list. head references the
first node in the list.
434 ==> 231 ==> 111 ==> 234 =>null
head
What node is returned by the call ((head.next).next)
in the above list?
2. In Java, what does the last link in
a non-circular linked list point to?
3. What is one benefit of a linked list
over an array for storing data?
4.
What
is the worst case performance for the following operations in Big O notation. Assume that the list has n nodes.
a. Inserting a node to the beginning of a list (prepending)
b. Inserting a node to the end of a list (appending)
c. Updating a node in a linked list
d. Cloning a list
e. Reversing a list
5.
The
following function is supposed to return the length of a linked list. What are
some of the problems with the method?
public int length(Node Head)
{
int size = 0;
Node cur;
while(cur != NULL){
size++;
cur = cur.next;
}
}
6.
Assume
that L is a linked list of at least 2 nodes. We need to insert the node N
(assume node reference is N) between head and the next node. Write the code
fragments that can be used to do this.
7. Suppose that you are allowed to use as much memory as you possibly want. How can we use this to reduce the time to insert a node to the end of a list from O(n) to O(1)?
8. Suppose we have a linked list of two nodes. Write a one line of code that will convert the linked list into a circular linked list.
9.
Any
object can be cloned using java’s clone method. Is it possible to clone a
linked list using the clone method? Suppose we have the following code.
LinkedList firstL =
new LinkedList();
LinkedList secondL =
firstL.clone();
Write a tester that can
test if secondL is a “deep copy” or “shallow copy” of
the first list.
10. What is the memory overhead of
maintaining data as a linked list as opposed to an array? Assume that we have
an array of n integers and a linked list of n nodes each with an integer as
data and a reference to the next node. Assuming that java references or
addresses are 4 bytes long, how much memory is needed to store the array of
integers and how much memory is needed to store the linked list of nodes?
ANSWERS
1.
The node 111 is referred to as (head.next).next.
This is the 3rd node in the list
2.
Last node points to null to indicate the end of the list
3.
Linked lists are lot more flexible in memory management compared to
arrays. Arrays need contiguous memory while linked list nodes are added or
deleted as needed.
4.
(a) O(1) (b) O(n) if there is no reference to last
node. O(1) otherwise (c) O(n) to find
an update the node (d) O(n) to clone a list (e) O(n) to reverse a list
5.
public int
length(Node Head) {
int size = 0;
Node cur; ç====== not initialized to
head
while(cur != NULL){
size++;
cur = cur.next;
}
ç====== need to return the size
}
6.
N.next = head.next; head.next = N;
7.
If there is no
reference to last node, then we need spend O(n)
operations to find the last node. Instead, if a pointer to last node is
maintained, then a node can be appended to a list in O(1)
operations.
8.
(head.next).next
= head;
9.
Change the value of a
node in secondL. Traverse the firstL
list to see if the same node has changed in firstL.
If so, then secondL is a shallow copy. Otherwise secondL is a deep copy.
10. Array of integers :
4n bytes, Linked list of
integers: 8n bytes