Linked Lists in C

Linked lists are ordered collections of data where each elements stores the location of the next element. Each element therefore contains two parts, the data and the link. The link is used to chain the elements together.

A list must at least have one separate pointer to the first element in the list; the name of this pointer is synonymous with the name of the list. This pointer is known as the head pointer, as it points to the head of the list.

Linked lists are made up of nodes. A node in a linked list is a structure that should have at least two fields, one for the data and one for the link. Nodes are self-referential structures in that each instance of the node structure should have a pointer to another instance of the same type.

typedef struct aNode {
	int data;
	struct aNode *link;
} LIST_NODE;

We can define an empty linked list as a single pointer that has the value NULL.

Let’s create a function that allocates memory for the node, assigns the data, and sets the link field to NULL.

LIST_NODE *createNode(int data) {
	LIST_NODE *newNode = (LIST_NODE *)malloc(sizeof(LIST_NODE));
	newNode->data = data;
	newNode->link = NULL;
	return newNode;
}

As there is no physical relationship between the nodes in a linked list in terms of where they are placed in memory, it is vital to ensure that each node links correctly to the next. Functions that insert or delete a node should return the head of the list; if the head has not been changed, then they simply return the original head address.

We will create three functions for adding and inserting nodes. The first function will simply append one node after another. The second function will set a node as the head of the list. The third function will insert a node at a specific location in the list.

//returns location of new node added to the list
LIST_NODE *appendNode(LIST_NODE *pre, LIST_NODE *theNode) {
	if (pre != NULL) {
                //if pre is at the end of the list
                //pre->link is NULL
                theNode->link = pre->link;
		pre->link = theNode;
	}
	return theNode;
}

LIST_NODE *setHead(LIST_NODE *head, LIST_NODE *theNode) {
	if (head != NULL) {
		theNode->link = head;
	}
	return theNode;
}

LIST_NODE *insertNode(LIST_NODE *head, LIST_NODE *pre, LIST_NODE *theNode) {
	LIST_NODE *returnHead = NULL;

	//if the head is not null, set it as the default return value
	//otherwise set it to pre
	if (head != NULL) {
		returnHead = head;
	}
	else {
		returnHead = pre;
	}
	
	//if the preceding node is the start of the list
	//or both pre and head are NULL
	if (head == pre) {
		//set new node as the head of the list
		returnHead = setHead(pre, theNode);
	} else {
		//inserting at middle or end
		//leave head as it was set initially
		appendNode(pre, theNode);
	}

	return returnHead;
}

Since every new node created has its link set automatically to null by the function that creates the node, we can be sure that any node we add to the end of the list will automatically end the list.

Since the first node of the list is stored in the head pointer, it is easy to append a new node to the beginning of the list, and make it the new head pointer.

To delete a node, we must remove it from the linked list by altering the pointers and then physically removing the node from heap memory. To delete  a node, we must have its location, given by its predecessor. We can then alter the links and return the memory to the heap using free().

LIST_NODE *deleteHead(LIST_NODE *head) {
	return deleteNode(head, NULL);
}

LIST_NODE * deleteNode(LIST_NODE *head, LIST_NODE *pre) {
	LIST_NODE *target;
	//deleting first node
	if (pre == NULL) {
		target = head;
		head = head->link;
	} //deleting other nodes
	else { 
		target = pre->link;
		pre->link = target->link;
	}

	free(target);
	return head;
}

To delete or insert a node, we must first find the node that precedes it. To do so, we must find the logical predecessor of the target node. We can design a search function to find a node based on an offset number from the head of the list, or we can design a search function find the last node in the list, or we can search the list to find a node with a particular value.

//returns a pointer to the node at the 0-index offset from the head
LIST_NODE *findByIndex(LIST_NODE *head, int offset) {
	int i = 0;
	LIST_NODE *prev = head;
	LIST_NODE *current = head->link;
	while (i++ < offset && current != NULL) { 		
               prev = current; 		
               current = current->link;
	}
	//previous node always holds value at the index 
	//if it exists
	return prev;
}

//finds and returns first match for the data value
LIST_NODE *findByDataValue(LIST_NODE *head, int dValue) {
	LIST_NODE *current = head;
	bool found = false;
	do {
		if (current->data == dValue) {
			found = true;
		}
		else {
			current = current->link;
		}
	} while (current != NULL && found == false);

	return current;
}

//find predecessor
LIST_NODE *findPredecessor(LIST_NODE *head, LIST_NODE *target) {
	LIST_NODE *predecessor = head;
	while (predecessor->link != target) {
		predecessor = predecessor->link;
	}
	return predecessor;
}

Any application that must process the entire list will use list traversal logic. To traverse the list, we will need to start at the beginning and work with each node in succession. A simple function for printing the entire list would involve starting at the head, printing the data stored in the head, checking to see if the next node is null, and if not, setting the current node to the next node, and repeating this process until the next node is null.

//print list
void printList(LIST_NODE *head) {
	LIST_NODE *current = head;
	while (current != NULL) {
		printf("%d\t", current->data);
		current = current->link;
	}
	printf("\n\n");
}

Let’s tie it all together in the main() function.

int main()
{
	LIST_NODE *head = createNode(1138);
	LIST_NODE *current = createNode(73);
	LIST_NODE * newNode = createNode(1701);
	LIST_NODE * deleteNodePred = NULL;

	appendNode(head, current);
	appendNode(current, newNode);

	current = createNode(1999);
	appendNode(newNode, current);

	newNode = createNode(73);
	current = appendNode(current, newNode);

	current = appendNode(current, createNode(3435));

	printList(head);

	newNode = createNode(389);

	appendNode(current, newNode);

	insertNode(head, newNode, createNode(404));

	insertNode(head, current, createNode(65537));

	printList(head);

	newNode = createNode(443);

	head = setHead(head, newNode);

	head = setHead(head, createNode(118));

	printList(head);

	deleteNodePred = findByIndex(head, 2);
	head = deleteNode(head, deleteNodePred);

	printList(head);

    return 0;
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s