Linked Lists : Linked lists are special list of some data elements linked to one another.
Each element pointing to the next element. Each element is called a node, which has two parts.
- INFO part which stores the information.
- POINTER which points to next element.
In singly linked list nodes have one pointer pointing to the next node.
Doubly linked list nodes have two pointers prev and next. Prev points to the previous node and next node points to the next node in the list.
Advantages :
- Linked lists are dynamic data structure : They can grow or shrink during the execution of a program.
- Efficient memory utilization.
- Insertion and Deletion are easier and efficient.
Disadvantages :
- More memory require, if the number of elements are more.
- Accessing the data element is time consuming.
Key terms :
- Data Fields
- Link fields
- NULL pointer : The link field of last node contains NULL.
- External Pointer : it’s a pointer to the very first element.
- Empty list : If nodes are not present in lists. START = NULL.
Representation of linear linked list
struct node
{
int data;
struct node *next;
};
typedef struct node NODE;
NODE *start;
Operation on linked lists :
- Creation
- Insertion
- Deletion
- Traversing
- Searching
- Concatenation
- Display
Linked Lists creation and display code :
#include<iostream>
#include<conio.h>
using namespace std;
struct node
{
int num;
node *ptr;
};
typedef struct node NODE;
class LinkedList
{
NODE *first, *head, *temp;
int count, choice;
public :
void insert();
void output();
LinkedList()
{
first = NULL;
count = 0;
choice = 1;
}
};
void LinkedList::insert()
{
while (choice)
{
head = new NODE;
cout << "Enter the data Element" << endl;
cin >> head->num;
if (first != NULL)
{
temp->ptr = head;
temp = head;
}
else
{
first = temp = head;
}
cout << " Do you want to continue : Type 1 or 0 " << endl;
cin >> choice;
}
}
void LinkedList::output()
{
temp->ptr = NULL;
temp = first;
cout << "Linked Lists Display :: " << endl;
while (temp != NULL)
{
cout << temp->num << endl;
count++;
temp = temp->ptr;
}
cout << "Number of items in Linked Lists :: " << count << endl;
}
$andip Patidar 