Transcript Linked Lists

Department of Computer Eng. & IT
Amirkabir University of Technology
(Tehran Polytechnic)
Data Structures
10 Questions on
Linked Lists
Lecturer: Abbas Sarraf ([email protected])
1
Write efficient code to reverse the order of the contents of a
singly linked list. Give the Big-Oh notation for the algorithm
Dept. of Computer Eng. & IT, Amirkabir University of Technology
2
Explain two different linked list variations (from a simply
singly linked list), and list a positive and negative factor for
each variation.
Dept. of Computer Eng. & IT, Amirkabir University of Technology
3
Crazy lists. Someone has written a class that creates CrazyLists.
These are linked lists made up of singly linked nodes. But
instead of making a nice sequential list, the class creates crazy
linked structure. Some nodes data field point to other nodes
instead of data. This leads to a branching structure that could
look like this:
myHead
data
next
myTail
Dept. of Computer Eng. & IT, Amirkabir University of Technology
Notes:
all data pointers that are not shown are pointing to non-Node objects or are nul
l.
Write a method that determines the distance (number of links) from the head n
ode to the tail node.
the tail node could be pointing at ANY of the nodes in the structure
There will be only one path from myHead to myTail
the Crazy list will not contain cycles, circular references that create loops in th
e structure.
Dept. of Computer Eng. & IT, Amirkabir University of Technology
4
The following function is supposed to return the length of a linked list.
What is wrong?
int length(NodePtr Head) {
int size = 0;
NodePtr cur;
while(cur != NULL){
size++;
cur = cur->next;
}
}
Dept. of Computer Eng. & IT, Amirkabir University of Technology
5
The following function is supposed to recursively return the length of a
linked list. What is wrong?
int lengthRec(NodePtr Head) {
if(Head)
return 0;
return length(Head);
}
Dept. of Computer Eng. & IT, Amirkabir University of Technology
6
The following function is supposed to merge two linked lists. What is
wrong?
NodePtr mergeLists(NodePtr Head1, NodePtr Head2){
NodePtr Union, Cur;
Union = Head1;
Cur = Head2;
while(Cur != NULL){
if(searchNode(Union, Cur->data))
insertNode(Union, Cur->data);
Cur = Cur->next;
}
return Head1;
}
Dept. of Computer Eng. & IT, Amirkabir University of Technology
7
The following function is supposed to print a Circular linked list.
What is wrong?
void print(NodePtr Rear){
NodePtr Cur;
Cur = Rear;
while(Cur!=NULL){
cout << Cur->data << " ";
Cur = Cur->next;
}
cout << endl;
}
Dept. of Computer Eng. & IT, Amirkabir University of Technology
8
The following function is supposed to insert a node in an ordered
Circular linked list. What is wrong?
void insertNode(NodePtr Rear, int item){
NodePtr New, Cur, Prev;
New = new Node;
New->data = item;
if(Rear == NULL){
// insert into empty list
Rear = New;
return;
}
Prev = NULL;
Cur = Rear;
do{
if(item <= Cur->data)
break;
Prev = Cur;
Cur = Cur->next;
}while(Cur != Rear);
New->next = Cur;
Prev->next = New;
}
Dept. of Computer Eng. & IT, Amirkabir University of Technology
9
The following function is supposed to delete a node in an ordered
Circular linked list. What is wrong?
void deleteNode(NodePtr& Rear, int item){
NodePtr Cur, Prev;
Prev = Rear;
Cur = Rear->next;
do{
// find Prev and Cur
if(item <= Cur->data)
break;
Prev = Cur;
Cur = Cur->next;
}while(Cur != Rear->next);
if(Cur->data != item){
// data does not exist
cout << "Data Not Found" << endl;
return;
}
if(Cur == Rear)
// revise Rear pointer if
deleting end
Rear = Prev;
Prev->next = Cur->next; // revise pointers
delete Cur;
}
Dept. of Computer Eng. & IT, Amirkabir University of Technology
10
‫ خروجي هر يك از شبه كدهاي زير را مشخص‬،‫با توجه به ليست داده شده در زير‬
.‫كنيد‬
first
0
2
node *what(node *p)
{
if (p && p->link)
return what(p->link->link);
else
return p;
}
node *q=what(first);
cout<<q->data;
Dept. of Computer Eng. & IT, Amirkabir University of Technology
4
6
8

void what(node *p)
{
if (p&& p->link)
{
what(p->link->link);
cout<<p->data;
what(p->link->link);
}
}
what(first);