Linked Lists in 15 Minutes !!!

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.

  1. INFO part which stores the information.
  2. 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 :

  1. Linked lists are dynamic data structure : They can grow or shrink during the execution of a program.
  2. Efficient memory utilization.
  3. Insertion and Deletion are easier and efficient.

Disadvantages :

  1. More memory require, if the number of elements are more.
  2. Accessing the data element is time consuming.

Key terms :

  1. Data Fields
  2. Link fields
  3. NULL pointer :  The link field of last node contains NULL.
  4. External Pointer :  it’s a pointer to the very first element.
  5. 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 :

  1. Creation
  2. Insertion
  3. Deletion
  4. Traversing
  5. Searching
  6. Concatenation
  7. 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;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s