3.4 Elementary Data Structures: Elementary List Processing

Question 1

What is list processing?

Answer 1

Working with data organized in linked lists is called list processing.

Question 2

Discuss a way to reverse a singly linked list.

Answer 2

By maintaining 3 pointers, say r, y and t.
Let x point to the first link of the initial linked list.
start by declaring
link r = NULL, y = x, t;

The link r will point to the portion of the list already processed.
The link y will point to the portion of the list not yet seen.
The link t will point to the node after y.

while( y != NULL)
{
   t = y->next;
   y->next = r;
   r = y;
   y = t;
}

now r will contain the reference to the first node of the reversed linked list ( last node of the original one). The last node of the reversed list will point to NULL.

we can then return r;

THE WHOLE FUNCTION IS:
link reverse(link x)
{
    link r = NULL, y = x, t;
    while( y != NULL)
    {
        t = y->next;
        y->next = r;
        r = y;
        y = t;
    }
    return r;
}

Question 3

What is insertion sort?

Answer 3

https://www.geeksforgeeks.org/insertion-sort/

Question 4

What are the differences between insertion sort and bubble sort?

Answer 4

https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms

Question 5

How to implement insertion sort in linked lists?

Answer 5

struct node heada, headb;
link t, u, x, a = &heada, b;
int i;

/* the list a contains random integers from 0-99 */
	a->next = NULL;
	for (i = 0, t = a; i < N; ++i)
	{
		t->next = malloc(sizeof(*t));
		t = t->next; t->next = NULL;
		t->item = rand() % 100;
	}

b = &headb; b->next = NULL;

/* in each iteration of the outer for loop, one node is removed from a and added somewhere inside b */

	for (t = a->next; t != NULL; t = u)
	{
		u = t->next;
		for (x = b; x->next != NULL; x = x->next)
			if (x->next->item > t->item) break;
		t->next = x->next; x->next = t;
	}

Question 6

What are online and offline algorithms?

Answer 6

https://stackoverflow.com/questions/11496013/what-is-the-difference-between-an-on-line-and-off-line-algorithm#:~:text=An%20algorithm%20is%20said%20to,of%20the%20data%20in%20advance.&text=An%20on%2Dline%20algorithm%20is,in%20response%20to%20each%20request.

Question 7

What are some head and tail conventions in linked lists?

Answer 7

pg 117

Question 8

What are doubly linked lists?

Answer 8

Doubly linked lists are lists which have nodes containing links to both the previous (prev) and the next (next) node, such that a link t, t->next->prev and t->prev->next are all the same thing.

Question 9

What are some benefits of a doubly linked list over a singly linked list?

Answer 9

1. Since we have the prev pointer, we can move backwards from a given node, which we cannot do in singly linked lists. So, we can implement operations such as:
   
   • find the item before a given item.
   • insert a node before a given node.
   • delete the node before a given node.
2. To delete a given node, the information contained within itself is more than sufficient. In singly linked lists, we need the pointer from the node which comes before the node to be deleted.
   To delete a node n,
   
   • set n->prev->next = n->next;
   • set n->next->prev = n->prev;

Question 10

What are the disadvantages of a doubly linked list?

Answer 10

1. The space required for linking one node to the other is doubled.
2. The number of link manipulations per basic operation is also doubled.

Question 11

When to use dummy heads nodes and when to use head pointers to refer to the first nodes?

Answer 11

• Dummy head nodes are used when we need a “pointer to the head node”. They are helpful in operations where the first node changes frequently like inserting at the first position.
• Head Pointers referencing a first node are useful when we just need to keep a track of the starting point of the list. They are not useful when the list’s start frequently changes.