ptr1(1200) ptr2(1400) ptr3(NULL)
+-------------+ +-------------+ +---------------+
| 25 |ptr1 -|---->| 30 | ptr2 -|---->| 40 | ptr3 -|--->X
+-------------+ +-------------+ +---------------+
n1(1000) n2(1200) n3(1400)
n1(node1), n2(node2) n3(node3) - nodes
ptr1(1200) - pointer to node2 with address 1200
ptr2(144) - pointer to node3 with address 1400
ptr3 - pointer of the last node always points to NULL.
Structure of a node:
struct node {
int data;
struct node *next;
};
+---------------------------------+
| data | next |
+---------------------------------+
node
How to create a node in linked list?
Dynamically allocate memory for the new node, fill the given data in it and return the new node to the caller.
struct node createNode(int data) {
struct *newnode = (struct node *)malloc(sizeof (struct node))
newnode->data = data;
newnode->next = NULL;
return (newnode);
}
How to insert a node into a linked list?
next(1200) next(1400) next(NULL)
+-------------+ +--------------+ +--------------+
| 25 |next -|---->| 30 | next -|---->| 40 | next -|--->X
+-------------+ +--------------+ +--------------+
n1(1000) n2(1200) n3(1400)
Insert a new node(n4) after node n2.
Traverse the list from the head node(n1) to the node(n2) after which the new node needs to be inserted.
n4 = createNode(50);
n4->next = n2->next;
n2->next = newnode;
Note: n4 is the new node here
next(1200) next(1500) next(1400) next(NULL)
+-------------+ +--------------+ +-------------+ +---------------+
| 25 |next -|-->| 30 | next -|-->| 50 | next -|-->| 40 | next -|--->X
+-------------+ +--------------+ +-------------+ +---------------+
n1(1000) n2(1200) n4(1500) n3(1400)
How to delete a node from a linked list?
next(1200) next(1500) next(1400) next(NULL)
+-------------+ +--------------+ +-------------+ +--------------+
| 25 |next -|-->| 30 | next -|-->| 50 | next -|-->| 40 | next -|--->X
+-------------+ +--------------+ +-------------+ +--------------+
n1(1000) n2(1200) n4(1500) n3(1400)
Traverse the list from the head node(n1) to the node(n2) that is present previous to the node(n4) which needs to be deleted.
temp = n2->next; // temp points to node n4
n2->next = temp->next; // n2->next points to node n3
free(temp); // delete node n4
next(1200) next(1400) next(NULL)
+-------------+ +--------------+ +--------------+
| 25 |next -|---->| 30 | next -|---->| 40 | next -|--->X
+-------------+ +--------------+ +--------------+
n1(1000) n2(1200) n3(1400)
How to search a node in a linked list?
Traverse the list from the head node(n1) until we find a node with the given value. If we have traversed the entire list and could not find a node with the given value, then the given data is not present in the list.
struct node * searchNode(int data) {
struct node *temp = n1; //n1 is the head node
while (temp) {
if (temp->data == data) {
printf("Data Present\n");
return temp;
}
temp = temp->next;
}
return NULL;
}
C Program To Implement Singly Linked List:
#include<stdio.h>
#include<stdlib.h>
struct node* createNode(int);
struct node* findNode(int);
void insertAtStart(int);
void insertAtEnd(int);
void insertAtPos(int, int);
void findNext(int);
void findPrevious(int);
void deleteList();
void deleteElement(int);
void isListExist();
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
/*
* creates node and fill the given data
*/
struct node * createNode(int data) {
struct node *ptr = (struct node *) malloc(sizeof (struct node));
ptr->data = data;
ptr->next = NULL;
return ptr;
}
void insertAtStart(int data) {
struct node *ptr = createNode(data);
/*
* if head is NULL, list not yet created. So,
* head and tail will be newly created node
*/
if (head == NULL) {
head = ptr;
tail = ptr;
return;
}
/*
* Adding node at the beginning of the list
* and the newly created node is the head hereafter
*/
ptr->next = head;
head = ptr;
}
void insertAtEnd(int data) {
struct node *ptr = createNode(data);
/*
* if tail is NULL, list not yet created. So.
* head and tail will be newly created node.
*/
if (tail == NULL) {
head = ptr;
tail = ptr;
}
/*
* Adding node at the end of the list and the
* newly created node is the tail here after
*/
tail->next = ptr;
tail = ptr;
}
void insertAtPos(int pos, int data) {
struct node *temp, *ptr = createNode(data);
int i = 1, inserted = 0;
/*
* if head is NULL and position is 1, it means
* user requests to create a first node of the
* list
*/
if (head == NULL || pos == 1) {
if (!head) {
head = ptr;
tail = ptr;
return;
}
ptr->next = head;
head = ptr;
return;
}
temp = head;
while (temp) {
/* inserting node at the give postion */
if (pos == i + 1) {
ptr->next = temp->next;
temp->next = ptr;
/*
* if the node is inserted at the end
* then the newly attached node is tail
*/
if (ptr->next == NULL)
tail = ptr;
inserted = 1;
break;
}
i++;
temp = temp->next;
}
if (!inserted)
printf("u ve entered wrong position\n");
}
struct node* findNode(int data) {
struct node *ptr;
int found = 0;
ptr = head;
while (ptr) {
/*
* searching for 1st occurance of data in
* linked list
*/
if (ptr->data == data) {
found = 1;
break;
}
ptr = ptr->next;
}
if (found)
return (ptr);
else
return (NULL);
}
void findPrevious(int data) {
struct node *ptr;
int found = 0;
ptr = head;
while (ptr != NULL && ptr->next != NULL) {
if (ptr->next->data == data) {
found = 1;
break;
}
ptr = ptr->next;
}
if (found)
printf("Value present previous to %d is %d\n",
data, ptr->data);
else
printf("No prev data available for ur input\n");
}
void findNext(int data) {
struct node *ptr;
int found = 0;
ptr = head;
while (ptr && ptr->next != NULL) {
if (ptr->data == data) {
found = 1;
break;
}
ptr = ptr->next;
}
if (found)
printf("Value present next to %d is %d\n",
data, ptr->next->data);
else
printf("No next data available for ur input\n");
}
void deleteNode(int data) {
struct node *ptr, *temp;
int res = 0;
ptr = head;
if (ptr->data == data) {
if (ptr->next == NULL) {
free(ptr);
head = tail = NULL;
}
head = ptr->next;
free(ptr);
return;
}
while (ptr != NULL && ptr->next != NULL) {
if (ptr->next->data == data) {
temp = ptr->next;
ptr->next = temp->next;
/*
* if last node is deleted, update tail value
*/
if (ptr->next == NULL)
tail = ptr;
free (temp);
res = 1;
}
ptr = ptr->next;
}
if (!res)
printf("Operation failed - Give data unavailable in list\n");
}
void deleteList() {
struct node *ptr;
ptr = head;
while (ptr){
head = ptr->next;
free(ptr);
ptr = head;
}
}
void walkList() {
struct node *ptr;
int i = 1;
ptr = head;
while (ptr) {
printf("+--------------------------+\n");
printf("|Node[%d] addr:%10u |\n", i, (unsigned int) ptr);
printf("+--------------------------+\n");
printf("|data = %3d |\n", ptr->data);
printf("+--------------------------+\n");
printf("|next = %10u |\n", (unsigned int)ptr->next);
printf("+--------------------------+\n");
ptr = ptr->next;
if (ptr) {
printf(" || \n");
printf(" || \n");
printf(" \\/ \n");
}
i++;
}
}
void isListExist() {
if (head)
printf("List is available\n");
else
printf("List is unavailable\n");
}
int main () {
int flag = 1, ch, data, pos, result;
while (flag) {
printf("########################################\n");
printf("1. Insertion at the start of List\n");
printf("2. Insert at the end of list\n");
printf("3. Insert at node at the given position\n");
printf("4. Find node\n");
printf("5. Find Previous data value\n");
printf("6. Find next data value\n");
printf("7. Delete node\n");
printf("8. Delete list\n");
printf("9. Walk list\n");
printf("10. Is list exists\n");
printf("11. Exit\n");
printf("########################################\n");
printf("Enter ur choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter data to insert into list\n");
scanf("%d", &data);
insertAtStart(data);
break;
case 2:
printf("Enter data to insert into list\n");
scanf("%d", &data);
insertAtEnd(data);
break;
case 3:
printf("Enter value for position and data\n");
scanf("%d%d", &pos, &data);
insertAtPos(pos, data);
break;
case 4:
printf("Enter value for data to be searched\n");
scanf("%d", &data);
struct node *ptr = findNode(data);
if (ptr)
printf("Give node is present in the list-"
"data:%d\n", ptr->data);
else
printf("Give data is not available in list\n");
break;
case 5:
printf("Enter value to get previous value\n");
scanf("%d", &data);
findPrevious(data);
break;
case 6:
printf("Enter value to get next value\n");
scanf("%d", &data);
findNext(data);
break;
case 7:
printf("Enter value to delete node\n");
scanf("%d", &data);
deleteNode(data);
break;
case 8:
deleteList();
break;
case 9:
walkList();
break;
case 10:
isListExist();
break;
case 11:
flag = 0;
break;
default:
printf("Pleae retry once again\n");
break;
}
printf("\n\n");
}
}
Output: (Singly Linked List Example)
Output: (Singly Linked List Example)
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:1
Enter data to insert into list
10
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:1
Enter data to insert into list
20
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:2
Enter data to insert into list
30
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:9
+--------------------------------+
|Node[1] addr: 157687832 |
+--------------------------------+
|data = 20 |
+--------------------------------+
|next = 157687816 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[2] addr: 157687816 |
+--------------------------------+
|data = 10 |
+--------------------------------+
|next = 157687848 |
+-------------------------------+
||
||
\/
+--------------------------------+
|Node[3] addr: 157687848 |
+--------------------------------+
|data = 30 |
+--------------------------------+
|next = 0 |
+--------------------------------+
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:3
Enter value for position and data
2 40
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:9
+--------------------------------+
|Node[1] addr: 157687832 |
+--------------------------------+
|data = 20 |
+--------------------------------+
|next = 157687864 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[2] addr: 157687864 |
+--------------------------------+
|data = 40 |
+--------------------------------+
|next = 157687816 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[3] addr: 157687816 |
+--------------------------------+
|data = 10 |
+--------------------------------+
|next = 157687848 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[4] addr: 157687848 |
+--------------------------------+
|data = 30 |
+--------------------------------+
|next = 0 |
+--------------------------------+
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:4
Enter value for data to be searched
10
Give node is present in the list-data:10
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:5
Enter value to get previous value
10
Value present previous to 10 is 40
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:6
Enter value to get next value
40
Value present next to 40 is 10
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:7
Enter value to delete node
40
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:9
+--------------------------------+
|Node[1] addr: 157687832 |
+--------------------------------+
|data = 20 |
+--------------------------------+
|next = 157687816 |
+--------------------------------+
||
||
\/
+---------------------------------+
|Node[2] addr: 157687816 |
+---------------------------------+
|data = 10 |
+---------------------------------+
|next = 157687848 |
+---------------------------------+
||
||
\/
+--------------------------------+
|Node[3] addr: 157687848 |
+--------------------------------+
|data = 30 |
+--------------------------------+
|next = 0 |
+--------------------------------+
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:8
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:10
List is unavailable
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:11
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:1
Enter data to insert into list
10
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:1
Enter data to insert into list
20
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:2
Enter data to insert into list
30
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:9
+--------------------------------+
|Node[1] addr: 157687832 |
+--------------------------------+
|data = 20 |
+--------------------------------+
|next = 157687816 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[2] addr: 157687816 |
+--------------------------------+
|data = 10 |
+--------------------------------+
|next = 157687848 |
+-------------------------------+
||
||
\/
+--------------------------------+
|Node[3] addr: 157687848 |
+--------------------------------+
|data = 30 |
+--------------------------------+
|next = 0 |
+--------------------------------+
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:3
Enter value for position and data
2 40
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:9
+--------------------------------+
|Node[1] addr: 157687832 |
+--------------------------------+
|data = 20 |
+--------------------------------+
|next = 157687864 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[2] addr: 157687864 |
+--------------------------------+
|data = 40 |
+--------------------------------+
|next = 157687816 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[3] addr: 157687816 |
+--------------------------------+
|data = 10 |
+--------------------------------+
|next = 157687848 |
+--------------------------------+
||
||
\/
+--------------------------------+
|Node[4] addr: 157687848 |
+--------------------------------+
|data = 30 |
+--------------------------------+
|next = 0 |
+--------------------------------+
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:4
Enter value for data to be searched
10
Give node is present in the list-data:10
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:5
Enter value to get previous value
10
Value present previous to 10 is 40
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:6
Enter value to get next value
40
Value present next to 40 is 10
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:7
Enter value to delete node
40
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:9
+--------------------------------+
|Node[1] addr: 157687832 |
+--------------------------------+
|data = 20 |
+--------------------------------+
|next = 157687816 |
+--------------------------------+
||
||
\/
+---------------------------------+
|Node[2] addr: 157687816 |
+---------------------------------+
|data = 10 |
+---------------------------------+
|next = 157687848 |
+---------------------------------+
||
||
\/
+--------------------------------+
|Node[3] addr: 157687848 |
+--------------------------------+
|data = 30 |
+--------------------------------+
|next = 0 |
+--------------------------------+
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:8
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:10
List is unavailable
########################################
1. Insertion at the start of List
2. Insert at the end of list
3. Insert at node at the given position
4. Find node
5. Find Previous data value
6. Find next data value
7. Delete node
8. Delete list
9. Walk list
10. Is list exists
11. Exit
########################################
Enter ur choice:11
No comments:
Post a Comment