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 structaNode{ int data; structaNode*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 listLIST_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 headLIST_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 valueLIST_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 predecessorLIST_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; }