C++ programming language part- 74 Linked List
Linked List
A linked list is a chain of
structures in which each structure contains of data as well as pointer, which
stores the address of the next logical structure in the list. We will discuss
about some programs allow the user to create a linked list in reverse. An
element in a linked list is called a node.
Each node has two parts: the first part contains the information and second
part is a pointer, which contains the address of next node. A linked list is
identified by a collection of nodes, and, a pointer called start, which has the address of the first node of the list. The
operation that can be performed on linked lists are: Insertion of Node, Deletion of Node, Traversal of list.
The class definition and
operation for list is as follows:
class list
{ private:
node
*start; // data type is node
public:
list() // The constructor
void
add_node();
void
delete_node();
void
traversal(); };
Inserting a Node
This involves adding a new node to the
linked list. The following sequence performs the insertion of a node in the
beginning of the list:
Step 1: Allocate memory for a new node
Step 2: Accept data for the Information part of the node
Step 3: Modify the content of the Start pointer so that it points to
the new node
Step 4: modify the content of the next node.
The
add_node() function is defined as follows:
Void
list::add_node()
{
node
*Fresh;
Fresh
= new node;
Fresh->add_word(); // member function of class node
Fresh->next=start;
start=Fresh
Traversing a list
In
order to display the contents of a list, you have to traverse the list. The
following sequence performs the traversal of a list to display the Information
part of each node.
Step 1: Set a temporary pointer (Temp) to start
Step 2: Repeat step 2 and 4 until Temp is not equal to NULL
Step 3: Print the Information part of the node pointed to by Temp
Step 4: Advance the pointer Temp so that points to the next node
The traversal() function is defined as follows:
void list::traversal()
{
node *Temp;
for(Temp=Start;Temp!=NULL;Temp=Temp->Next)
{
Temp->display_node() // member function of node class
}
}
