Linked List in C : Implementation

What is Linked List?

Linked List is a Linear Data Structure, Just Like the Array but in Array, Elements are stored in the Contiguous memory Location whereas in Linked List they are not stored in this manner.

In the linked list the elements are linked with each other using pointers. It consists of items called “Nodes” which contain two parts. The first part stores the actual data and the second part has a pointer that points to the next node.

The structure of a linked list is shown in the below image.

Representation of Linked List:

Every element in the Linked List is called a Node. A Node has a value associated with it and the pointer pointing to the next Node. Let us define a Node using struct which has an int and Node* as its data members.

This is how we define a node in C using structures or “struct”.

struct Node  
{ 
   int val; 
   struct Node *next;
};


Linked List with 4 Nodes.

Operations Associated With LinkedList

Following operations are performed on Linked List.

Insert Node at Last:

C Program

void InsertatLast(int x) {

  struct Node * temp;
  temp = (struct Node * ) malloc(sizeof(struct Node));
  temp -> val = x;
  temp -> next = NULL;
  if (head == NULL) {
    head = temp;
    tail = temp;
  } else {
    tail -> next = temp;
    tail = tail -> next;
  }
}

Time Complexity: O(N)

Space Complexity: O(1)

Insert Node at First:

Code:

C Program

void InsertatFirst(int x) {
  struct Node * temp = (struct Node * ) malloc(sizeof(struct Node));
  temp -> val = x;
  temp -> next = NULL;
  if (head == NULL) {
    head = temp;
    tail = temp;
  } else {
    temp -> next = head;
    head = temp;
  }
}

Time Complexity: O(1)

Space Complexity: O(1)

Insert Node at any position:

Code:

C Program

void InsertAfter(int pos, int x) {
  struct Node * temp = (struct Node * ) malloc(sizeof(struct Node));
  temp -> val = x;
  temp -> next = NULL;
  int len = Length();
  if (pos > len) {
    printf("Pos is Invalid\n");
    printf("Linked List is having only %d Nodes \n", len);
    return;
  }
  struct Node * curr = head;
  while (--pos)
    curr = curr -> next;
  temp -> next = curr -> next;
  curr -> next = temp;
}

Time Complexity: O(N)

Space Complexity: O(1)

Delete Node at any Position:

Code:

C Program

void Delete(int pos) {
  int len = Length();//it gives the length of the linked list
  if (pos > len) {
    printf("Position is Invalid\n");
    printf("Linked List is having only %d Nodes \n", len);
    return;
  } else if (pos == 1) {
    struct Node * temp = head;
    head = temp -> next;
    temp -> next = NULL;
    free(temp);
  } else {
    struct Node * curr = head, * prev = NULL;
    int loc = pos;
    while (--loc) {
      prev = curr;
      curr = curr -> next;
    }
    prev -> next = curr -> next;
    curr -> next = NULL;
    free(curr);
    if (pos == len)
      tail = prev;
  }
}

Time Complexity: O(N)

Space Complexity: O(1)

Display Node values:

Code:

C Program

void Traverse() {
  struct Node * curr = head;
  printf("[ ");
  if (curr == NULL) {
    printf("Linked List is empty\n");
    return;
  }
  while (curr != NULL) {
    printf("%d ", curr -> val);
    curr = curr -> next;
  }
  printf(" ]");
  printf("\n");
}

Time Complexity: O(N)

Space Complexity: O(1)

Length of the Linked List:

Code:

C Program

int Length() {
  int nodescount = 0;
  struct Node * curr = head;
  for (; curr != NULL; curr = curr -> next)
    nodescount++;
  return nodescount;
}

Time Complexity: O(N)

Space Complexity: O(1)

Reverse Linked List:

Code:

C Program

void ReverseList() {
  struct Node * third = NULL, * second = NULL, * first = head;
  while (first) {
    third = second;
    second = first;
    first = first -> next;
    second -> next = third;
  }
  tail = head;
  head = second;
}

Time Complexity: O(N)

Space Complexity: O(1)

Search for Value in Linked List:

Code:

C Program

struct Node * SearchForValue(int x) {
  struct Node * curr = head;
  while (curr) {
    if (curr -> val == x)
      return curr;
    curr = curr -> next;
  }
  return NULL;
}

Time Complexity: O(N)

Space Complexity: O(1)

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article