Pointer - Based Linked Lists:
A linked list contains elements that are linked to one another. Each element, or node, contains both a data item - an integer, for example- and a "pointer"(address) to the next item.
A node in a linked list is usually a struct :
typedef struct node* ptrType; // pointer to node
Defining a pointer to a node:
ptrType P; or node* P;
Dynamically allocating a node:
P = new node; // allocates a node to which P points
Referencing a node member:
P -> Item // referencing the member Item of the node to which P points
Head:
The Head is an additional pointer whose sole purpose is to point to the first node on the linked list. Remember that each pointer in a linked list is a pointer to a struct, that is, an entire node; it is not a pointer to only the data portion of the node.
ptrType Head; // creates the variable Head, whose value is undefined.
If Head is NULL, the linked list is empty. Head is a pointer variable waiting to be assigned a value. You can assign NULL to Head without first using new.
Head = NULL;
Operations With Linked Lists:
Suppose you have a linked list and you want to display the data in the list.
Let a current pointer point to the first node in the linked list
while (the current pointer is not NULL)
{ Display the data portion on the current node
Set the current pointer to the Next pointer of the current node
} // end while
This solution requires that you keep track of the current position within the linked list.You need a pointer variable Cur that points to the current node. ptrType Cur = Head;
cout << Cur->Item << endl; // displays the data portion of the current node
Cur = Cur->Next; // advances the current position to the next node
for (ptrType Cur = Head; Cur != NULL; Cur = Cur->Next)
cout << Cur->Item << endl;
Cur points to each node in a nonempty linked list during the course of the for loop's execution, and so the data portion of each node is displayed. After the last node is displayed, Cur becomes NULL and the for loop terminates. When the list is empty(Head is Null) the for loop is correctly skipped.
Traverse- a traverse operation sequentially visits each node in the linked list until it reaches the end of the list. Displaying a linked list does not alter it.
Insert-Three steps to insert a new node into a linked list:
1. Determine the point of insertion.
2. Create a new node and store the new data in it.
3. Connect the new node to the linked list by changing pointers.
Delete-Three steps to delete a node from a linked list
1. Locate the node that you want to delete.
2. Disconnect this node from the linked list by changing pointers.
3. Return the node to the system.
Deleting an interior node:
Prev->Next = Cur->Next;
Deleting the first node is a special case:
Head = Head->Next;
When you delete the first node of the list, you must change the value of Head to reflect the fact that, after the deletion, the list has a new first node. That is, the node that was second prior to the deletion is now first.
Return deleted nodes to the system by using delete:
Cur->Next = NULL;
delete Cur;
Cur = NULL;
Retrieve