• Choose a category
• All
• Classic-Fiction

By Root 1474 0

answers at the end of the chapter. As with inserting an element, this call requires consideration of two cases: removing an element from the head of the list and removing one elsewhere.

The actual process of removing the element from the list is a simple one, but it too requires some care (see Figure 5.4). Generally, to remove an element from a linked list, we set the next pointer of the element preceding the one being removed to point to the element after the element being removed. However, when removing an element from the head of a list, there is no element that precedes the element being removed. Thus, in this case, we set the head of the list to point to the element after the one being removed. As with insertion, NULL serves nicely as a sentinel passed in element to indicate that the element at the head of the list should be removed. In addition to these tasks, whenever we remove the element at the tail of the list, we must update the tail member of the list data structure to point to the new tail, or to NULL if removing the element has caused the list to become empty. Last, we update the size of the list by decreasing the size member by 1. Upon return, data points to the data from the element removed.

Figure 5.4. Removing an element from a linked list

The runtime complexity of list_rem_next is O (1) because all of the steps in removing an element from a linked list run in a constant amount of time.

list_size, list_head, list_tail, list_is_tail,list_data, and list_next

These macros implement some of the simpler linked list operations (see Example 5.1). Generally, they provide an interface for accessing and testing members of the List and ListElmt structures.

The runtime complexity of these operations is O (1) because accessing and testing members of a structure are simple tasks that run in a constant amount of time.

Example 5.2. Implementation of the Linked List Abstract Datatype

/*****************************************************************************

* *

* -------------------------------- list.c -------------------------------- *

* *

*****************************************************************************/

#include

#include

#include "list.h"

/*****************************************************************************

* *

* ------------------------------- list_init ------------------------------ *

* *

*****************************************************************************/

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

/*****************************************************************************

* *

* Initialize the list. *

* *

*****************************************************************************/

list->size = 0;

list->destroy = destroy;

list->head = NULL;

list->tail = NULL;

return;

}

/*****************************************************************************

* *

* ----------------------------- list_destroy ----------------------------- *

* *

*****************************************************************************/

void list_destroy(List *list) {

void *data;

/*****************************************************************************

* *

* Remove each element. *

* *

*****************************************************************************/

while (list_size(list) > 0) {

if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy !=

NULL) {

/***********************************************************************

* *

* Call a user-defined function to free dynamically allocated data. *

* *

***********************************************************************/

list->destroy(data);

}

}

/*****************************************************************************

* *

* No operations are allowed now, but clear the structure as a precaution. *

* *

*****************************************************************************/

memset(list, 0, sizeof(List));

return;

}

/*****************************************************************************