Create Singly linked list in c

Linked list creation and traversal is the stepping stone in data structures. In this article, I will explain how to create and traverse a linked list in C programming. I will explain step by step process to create and traverse a linked list of n nodes and display its elements.

Nội dung chính Show

Required knowledge
How to create and traverse a linked list?
How to create a linked list?
How to traverse a linked list?
Example program to create and traverse a linked list
Representation of Linked List
Linked List Utility
Linked List Implementations in Python, Java, C, and C++ Examples
Linked List Complexity
Linked List Applications
Recommended Readings
1. Tutorials
2. Examples
Video liên quan

Write a C program to implement Singly linked list data structure. C program to create a linked list and display elements of linked list.

Required knowledge

Functions, Structures, Pointers, Dynamic Memory Allocation

How to create and traverse a linked list?

In previous article we discussed about singly linked list data structure, its need and advantages. Here we will learn to create and traverse a linked list in C program.

How to create a linked list?

Step by step descriptive logic to create a linked list.

The first step of creating linked list of n nodes starts from defining node structure. We need a custom type to store our data and location of next linked node. Let us define our custom node structurestruct node { int data; struct node *next; };
Where data is the data you want to store in list. *next is pointer to the same structure type. The *next will store location of next node if exists otherwise NULL.
Note: The node structure may vary based on your requirement. You can also have user defined types as node data section.
Declare a pointer to node type variable to store link of first node of linked list. Say struct node *head;.
Note: You can also declare variable of node type along with node structure definition.
Input number of nodes to create from user, store it in some variable say n.
Declare two more helper variable of node type, say struct node *newNode, *temp;.
If n > 0 then, create our first node i.e. head node. Use dynamic memory allocation to allocate memory for a node. Say head = (struct node*)malloc(sizeof(struct node));.
If there is no memory to allocate for head node i.e. head == NULL. Then print some error message and terminate program, otherwise move to below step.
Input data from user and assign to head using head->data = data;.
At first head node points to NULL. Hence, assign head->next = NULL;.
Now, we are done with head node we should move to creation of other nodes. Copy reference of head to some other temporary variable, say temp = head;. We will use temp to store reference of previous node.
Allocate memory and assign memory reference to newNode, say newNode = (struct node*)malloc(sizeof(node));.
If memory got allocated successfully then read data from user and assign to data section of new node. Say newNode->data = data;.
Make sure new node points to NULL.
Now link previous node with newly created node i.e. temp->next = newNode;.
Make current node as previous node using temp = temp->next;.
Repeat step 10-14 for remaining n - 2 other nodes.

How to traverse a linked list?

Step by step descriptive logic to traverse a linked list.

Create a temporary variable for traversing. Assign reference of head node to it, say temp = head.
Repeat below step till temp != NULL.
temp->data contains the current node data. You can print it or can perform some calculation on it.
Once done, move to next node using temp = temp->next;.
Go back to 2nd step.

Example program to create and traverse a linked list

/** * C program to create and traverse a Linked List */ #include #include /* Structure of a node */ struct node { int data; // Data struct node *next; // Address }*head; /* * Functions to create and display list */ void createList(int n); void traverseList(); int main() { int n; printf("Enter the total number of nodes: "); scanf("%d", &n); createList(n); printf("\nData in the list \n"); traverseList(); return 0; } /* * Create a list of n nodes */ void createList(int n) { struct node *newNode, *temp; int data, i; head = (struct node *)malloc(sizeof(struct node)); // Terminate if memory not allocated if(head == NULL) { printf("Unable to allocate memory."); exit(0); } // Input data of node from the user printf("Enter the data of node 1: "); scanf("%d", &data); head->data = data; // Link data field with data head->next = NULL; // Link address field to NULL // Create n - 1 nodes and add to list temp = head; for(i=2; i<=n; i++) { newNode = (struct node *)malloc(sizeof(struct node)); /* If memory is not allocated for newNode */ if(newNode == NULL) { printf("Unable to allocate memory."); break; } printf("Enter the data of node %d: ", i); scanf("%d", &data); newNode->data = data; // Link data field of newNode newNode->next = NULL; // Make sure new node points to NULL temp->next = newNode; // Link previous node with newNode temp = temp->next; // Make current node as previous node } } /* * Display entire list */ void traverseList() { struct node *temp; // Return if list is empty if(head == NULL) { printf("List is empty."); return; } temp = head; while(temp != NULL) { printf("Data = %d\n", temp->data); // Print data of current node temp = temp->next; // Move to next node } }

Enter the total number of nodes: 5 Enter the data of node 1: 10 Enter the data of node 2: 20 Enter the data of node 3: 30 Enter the data of node 4: 40 Enter the data of node 5: 50 Data in the list Data = 10 Data = 20 Data = 30 Data = 40 Data = 50

Happy coding 😉

A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node. For example,

Linked list Data Structure

You have to start somewhere, so we give the address of the first node a special name called HEAD. Also, the last node in the linked list can be identified because its next portion points to NULL.

Linked lists can be of multiple types: singly, doubly, and circular linked list. In this article, we will focus on the singly linked list. To learn about other types, visit Types of Linked List.

Note: You might have played the game Treasure Hunt, where each clue includes the information about the next clue. That is how the linked list operates.

Representation of Linked List

Let's see how each node of the linked list is represented. Each node consists:

A data item
An address of another node

We wrap both the data item and the next node reference in a struct as:

struct node { int data; struct node *next; };

Understanding the structure of a linked list node is the key to having a grasp on it.

Each struct node has a data item and a pointer to another struct node. Let us create a simple Linked List with three items to understand how this works.

/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;

If you didn't understand any of the lines above, all you need is a refresher on pointers and structs.

In just a few steps, we have created a simple linked list with three nodes.

Linked list Representation

The power of a linked list comes from the ability to break the chain and rejoin it. E.g. if you wanted to put an element 4 between 1 and 2, the steps would be:

Create a new struct node and allocate memory to it.
Add its data value as 4
Point its next pointer to the struct node containing 2 as the data value
Change the next pointer of "1" to the node we just created.

Doing something similar in an array would have required shifting the positions of all the subsequent elements.

In python and Java, the linked list can be implemented using classes as shown in the codes below.

Linked List Utility

Lists are one of the most popular and efficient data structures, with implementation in every programming language like C, C++, Python, Java, and C#.

Apart from that, linked lists are a great way to learn how pointers work. By practicing how to manipulate linked lists, you can prepare yourself to learn more advanced data structures like graphs and trees.

Linked List Implementations in Python, Java, C, and C++ Examples

# Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next

// Linked list implementation in Java class LinkedList { // Creating a node Node head; static class Node { int value; Node next; Node(int d) { value = d; next = null; } } public static void main(String[] args) { LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) { System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; } } }

// Linked list implementation in C #include #include // Creating a node struct node { int value; struct node *next; }; // print the linked list value void printLinkedlist(struct node *p) { while (p != NULL) { printf("%d ", p->value); p = p->next; } } int main() { // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); }

// Linked list implementation in C++ #include #include using namespace std; // Creating a node class Node { public: int value; Node* next; }; int main() { Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) { cout << head->value; head = head->next; } }

Linked List Complexity

Time Complexity

	Worst case	Average Case
Search	O(n)	O(n)
Insert	O(1)	O(1)
Deletion	O(1)	O(1)

Space Complexity: O(n)

Linked List Applications

Dynamic memory allocation
Implemented in stack and queue
In undo functionality of softwares
Hash tables, Graphs

1. Tutorials

2. Examples

Top List List

Create Singly linked list in c

Required knowledge

How to create and traverse a linked list?

How to create a linked list?

How to traverse a linked list?

Example program to create and traverse a linked list

Representation of Linked List

Linked List Utility

Linked List Implementations in Python, Java, C, and C++ Examples

Linked List Complexity

Linked List Applications

Recommended Readings

1. Tutorials

2. Examples

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội