CODEWITHSUNDEEP
calgorithmlinked-list
Nahua Kang
Nahua Kang

Reputation: 406

Implementation of Singly-Linked List from Loudon's Algorithm Book

I am reading Mastering Algorithms with C by Kyle Loudon, and currently I am struggling with Loudon's implementation of Singly-Linked List in Chapter 5.

Here are the links to the source code. I apologize for not posting them here as they are a bit long.

list.h

list.c

My question is related to the destroy in list.c as it is mentioned in line 11 under

void list_init(List* list, void (*destroy)(void* data))

as list->destroy = destroy

and then again in line 24 as

list->destroy(data).

All I know is that this destroy is different from the function list_destroy but I have no idea what it is. Is it a function or is it just a pointer? What purpose does it serve in the list_init() function for initializing a linked list?

I really appreciate your time and help! The source code is linked above.

Upvotes: 2

Views: 197

Answers (2)

btilly
btilly

Reputation: 46435

A linked list is a data structure made up of nodes, each of which contains or links to one piece of data.

The destroy function destroys just one node out of the list.

The list_destroy function destroys an entire list.

In the given implementation, the node actually contains a pointer to its destroy function, and accesses it by dereferencing that pointer. As it happens (so far), all nodes point to the same destroy function. But with more complex data structures this pattern allows multiple types of nodes to be in the data structure. And the equivalent of the list_destroy function will correctly destroy each node type correctly since the node knows how it should be destroyed.

Upvotes: 1

FlorianK
FlorianK

Reputation: 440

It is a function pointer. When you create an instance of this list, you also have to hand the init_list function a function which it will use to destroy the info.

The purpose of a linked list is to store information, and the linked list structure is there to give some structure to this data. Hence, each element of the list contains a pointer to some data, and a pointer to the next element in the list. However, you want the list to able to handle multiple kinds of data.

Suppose you want to remove an element of the list, then there are basically two things that have to happen:

  1. The data needs to be destroyed

  2. The linked list structure must be restored. Meaning that the predecessor of the element you removed must point to the next element in the list.

Since you do not know beforehand what kind of data the data pointer in the list will contain, for step 1 a function pointer is provided to handle the destroying of that data.

Upvotes: 2

Related Questions