Home » Data Structure

Singly Linked List implementation in C

In this program, we are implementing a single linked list in Data Structure using C program.

This is a data structure program using C, here we are implementing a singly linked list using C language program.

Code explanation for singly Linked List implementation

In this program,

• head and tail are two pointers, where head points to first node of linked list and tail points the las node of the linked list.
• A Node contains two parts
  1. item - item contains data item (it may be a number, string or any object like structure).
  2. next - next contains address of the next node.
• Last Node of the linked list contains NULL in the next part.

Singly Linked list program in C

#include <stdio.h>
#include <stdlib.h>

// Self referential structure to create node.
typedef struct tmp {
  int item;
  struct tmp *next;
} Node;

// structure for create linked list.
typedef struct {
  Node *head;
  Node *tail;

} List;

// Initialize List
void initList(List *lp) {
  lp->head = NULL;
  lp->tail = NULL;
}

// Create node and return reference of it.
Node *createNode(int item) {
  Node *nNode;

  nNode = (Node *)malloc(sizeof(Node));

  nNode->item = item;
  nNode->next = NULL;

  return nNode;
}

// Add new item at the end of list.
void addAtTail(List *lp, int item) {
  Node *node;
  node = createNode(item);

  // if list is empty.
  if (lp->head == NULL) {
    lp->head = node;
    lp->tail = node;
  } else {
    lp->tail->next = node;
    lp->tail = lp->tail->next;
  }
}

// Delete item from the end of list.
int delFromTail(List *lp) {
  Node *temp;
  int i = 0;

  int item = 0;

  if (lp->tail == NULL) {
    printf("\nList is Empty ...");
    return -1;
  } else {
    temp = lp->head;

    while (temp->next != lp->tail) {
      temp = temp->next;
    }

    item = lp->tail->item;

    lp->tail = temp;
    lp->tail->next = NULL;
  }

  return item;
}

// Add new item at begning of the list.
void addAtHead(List *lp, int item) {
  Node *node;
  node = createNode(item);

  // if list is empty.
  if (lp->head == NULL) {
    lp->head = node;
    lp->tail = node;
  } else {
    node->next = lp->head;
    lp->head = node;
  }
}

// Delete item from Start of list.
int delFromHead(List *lp) {
  int item = 0;

  if (lp->head == NULL) {
    printf("\nList is Empty ...");
    return -1;
  } else {
    item = lp->head->item;
    lp->head = lp->head->next;
  }

  return item;
}

// To print list from start to end of the list.
void printList(List *lp) {
  Node *node;

  if (lp->head == NULL) {
    printf("\nEmpty List");
    return;
  }

  node = lp->head;

  printf("\nList: \n\n\t");
  while (node != NULL) {
    printf("| %05d |", node->item);
    node = node->next;

    if (node != NULL) printf("--->");
  }
  printf("\n\n");
}

// Main function to execute program.
int main() {
  List *lp;

  int item = 0;

  lp = (List *)malloc(sizeof(List));

  initList(lp);

  addAtTail(lp, 10);
  addAtTail(lp, 20);
  addAtHead(lp, 30);
  addAtHead(lp, 40);

  printList(lp);

  item = delFromTail(lp);

  if (item >= 0) printf("\nDeleted item is : %d", item);
  printList(lp);

  item = delFromHead(lp);

  if (item >= 0) printf("\nDeleted item is : %d", item);
  printList(lp);

  return 0;
}

Output

List: 

	| 00040 |--->| 00030 |--->| 00010 |--->| 00020 |


Deleted item is : 20
List: 

	| 00040 |--->| 00030 |--->| 00010 |


Deleted item is : 40
List: 

	| 00030 |--->| 00010 |