1#include <iostream>
2using namespace std;
3
4// A linked list node
5struct Node
6{
7 int data;
8 struct Node *next;
9};
10//insert a new node in front of the list
11void push(struct Node** head, int node_data)
12{
13 /* 1. create and allocate node */
14 struct Node* newNode = new Node;
15
16 /* 2. assign data to node */
17 newNode->data = node_data;
18
19 /* 3. set next of new node as head */
20 newNode->next = (*head);
21
22 /* 4. move the head to point to the new node */
23 (*head) = newNode;
24}
25
26//insert new node after a given node
27void insertAfter(struct Node* prev_node, int node_data)
28{
29 /*1. check if the given prev_node is NULL */
30if (prev_node == NULL)
31{
32 cout<<"the given previous node is required,cannot be NULL"; return; }
33
34 /* 2. create and allocate new node */
35 struct Node* newNode =new Node;
36
37 /* 3. assign data to the node */
38 newNode->data = node_data;
39
40 /* 4. Make next of new node as next of prev_node */
41 newNode->next = prev_node->next;
42
43 /* 5. move the next of prev_node as new_node */
44 prev_node->next = newNode;
45}
46
47/* insert new node at the end of the linked list */
48void append(struct Node** head, int node_data)
49{
50/* 1. create and allocate node */
51struct Node* newNode = new Node;
52
53struct Node *last = *head; /* used in step 5*/
54
55/* 2. assign data to the node */
56newNode->data = node_data;
57
58/* 3. set next pointer of new node to null as its the last node*/
59newNode->next = NULL;
60
61/* 4. if list is empty, new node becomes first node */
62if (*head == NULL)
63{
64*head = newNode;
65return;
66}
67
68/* 5. Else traverse till the last node */
69while (last->next != NULL)
70last = last->next;
71
72/* 6. Change the next of last node */
73last->next = newNode;
74return;
75}
76
77// display linked list contents
78void displayList(struct Node *node)
79{
80 //traverse the list to display each node
81 while (node != NULL)
82 {
83 cout<<node->data<<"-->";
84 node = node->next;
85 }
86
87if(node== NULL)
88cout<<"null";
89}
90/* main program for linked list*/
91int main()
92{
93/* empty list */
94struct Node* head = NULL;
95
96// Insert 10.
97append(&head, 10);
98
99// Insert 20 at the beginning.
100push(&head, 20);
101
102// Insert 30 at the beginning.
103push(&head, 30);
104
105// Insert 40 at the end.
106append(&head, 40); //
107
108Insert 50, after 20.
109insertAfter(head->next, 50);
110
111cout<<"Final linked list: "<<endl;
112displayList(head);
113
114return 0;
115}
116