Scribd
Upload
643 views7 pages

Tutorial Linked List

The document discusses linked lists and provides examples of code snippets to perform operations on linked lists using single assignment statements or loops. It includes examples to initialize linked lists, insert and remove nodes, traverse lists, merge sorted lists, and convert lists to circular lists. The exercises demonstrate how to manipulate linked lists by modifying the pointers to move between nodes in the list.

Uploaded by

Mohd Fadhrul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
643 views7 pages

Tutorial Linked List

The document discusses linked lists and provides examples of code snippets to perform operations on linked lists using single assignment statements or loops. It includes examples to initialize linked lists, insert and remove nodes, traverse lists, merge sorted lists, and convert lists to circular lists. The exercises demonstrate how to manipulate linked lists by modifying the pointers to move between nodes in the list.

Uploaded by

Mohd Fadhrul
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Tutorial 2

Topic Linked List

Use this declaration of the Node class:


struct Node {
    int info;
    Node * next;
};

Node * p;
Node * q;
Node * r;

Question 1

Initial Setup Exercise Final Configuration


Use a single assignment Figure:
statement to make the variable
p refer to the Node with info
'2'

Code:
p=p->next;

Use a single assignment Figure:


statement to assignment
statement must refer to both
variables p and q.

Code:
p=p->next;

Use a single assignment Figure:


statement to make the variable
q refer to the Node with info
'1'.

Code:
q=p;

Use a single assignment Figure:


statement to make the variable
r refer to the Node with info
'2'.
Code:
r=p->next;

Use a single assignment Figure:


statement to set the info of the
Node referred to by p equal to
the info of the Node referred to
by r (you must access this info 3
through r; do not refer to the
character '3' directly)
Code:
p=p->next->next->info;

Write a single assignment Figure:


statement to transform the
linked list headed by p into
a circular linked list. Your
assignment
statement must refer to both
variables p and r.

Code:
r->next=p;

Write a single assignment Figure:


statement to transform the
linked list headed by p into
a circular linked list. Your
assignment
statement must refer to both
variables p and q.

Code:
q->next->next=p;

Write a single assignment Figure:


statement to transform the
linked list headed by p into
a circular linked list. Your
assignment statement must
refer only to variable p.

Code:
p->next->next->next=p;
Question 2

Use this declaration of the Node class:


struct Node {
    char info;
    Node * next;
};

Node * p;
Node * q;
Node * r;

Initial Setup Exercise Final Configuration


Write a single assignment Figure:
statement to remove the Node
with info 'B' from the linked
list headed by p. Your
assignment
statement must refer to both
variables p and q.

Code:
p->next=q;

Write a single assignment Figure:


statement to remove the Node
with info 'B' from the linked
list headed by p

Code:
p->next=p->next->next;

Write a while loop to make q Figure:


refer successively to each
Node in the linked list headed
by p. q must end up referring
to the last Node in the list.

Code:
node * q=p;
while (q->next != NULL)
{
q=q->next;
}

Write a while loop to make q Figure:


refer successively to each
Node in the linked list headed
by p until q refers to the first
Node with info (lowercase) 'c'.

Code:
node * q=p;
while (q->next != ‘c’)
{
q=q->next;
}

Use four assignment Figure:


statements, each referring to
variable p, to create a linked
list headed by p and containing
4 Nodes with info 'A', 'B', 'C',
and 'D', in this order.

Code:
p->info=A;
p->next->info=B;
p->next->next->info=C;
p->next->next-next->info=D;

Create a new Node with info Figure:


'A' and insert it at the
beginning of the list headed by
p.

Code:
Node * q = new Node();
q->info = A;
q->next = p;
p = q;

Create a new Node with info Figure:


'D' and insert it at the end of
the list headed by p.
Code:
Node * newNode = new Node();
newNode->info = D;
newNode->next = NULL;

if (p == NULL)
{
p = newNode;
return;
}

else
{
Node * temp = p;

while (temp->next != NULL)


{
Temp=temp->next;
}
temp->next = newNode;
}

Remove the Node at the Figure:


beginning of the list headed by
p and insert it at the end of the
same list. Your
program must refer to both
variables p and q.

Code:
void deleteFirst ()
{
Node * q = p;
p=p->next;
delete q;
return p;
}

void insertLast ()
{
Node * q = new Node();
q->info = A;
q->next = NULL;

if (p == NULL)
{
p = q;
return;
}
else
{
Node * temp = p;

while (temp->next != NULL)


{
temp=temp->next;
}
temp->next = q;
}
}

Merge the two lists headed by Figure:


p and q into a single list
headed by p in which the
Nodes are sorted in
alphabetical order.

Code:
Void moveNode (struct Node**
destRef, struct Node** sourceRef)
{
If (*sourceRef == NULL)
return;
struct Node * newNode = *
sourceRef;
* sourceRef = (*sourceRef)-
>next;
newNode-> next = *destRef;
*destRef=newNode;
}

struct Node * sortedMerge (struct


Node * p, struct Node * q)
{
struct Node dummy;
dummy.next=NULL;

struct Node* tail = &dummy;


while ()
{
if (p == NULL)
{
tail->next=q;
break;
}

else if (p == NULL)
{
tail->next=q;
break;
}

if (p->info <= q->info)


moveNode (&(tail->next),
&p);

else
moveNode (&(tail->next),
&b);
}
return dummy.next;
}

Using only the three existing Figure:


variables p, q, and r, reverse
the order of the Nodes in the
list headed by p.

Code:
void reverse()
{
Node * r = p;
Node * q = NULL, * next =
NULL;

While (r != NULL)
{
next=r->next;
r->next=q;
q=r;
r=next;
}
p=q;
}

You might also like