—A list is a homogeneous collection of elements. Each element except the first one has a predecessor. Each element except the last one has a successor. Length of a linked list are the number of items in the list.

A linked list can be sorted or unsorted. —An unsorted list is a list in which data items are placed in no particular order. —A list in which data items are placed in a particular order is called a sorted list.

—Data is stored in a linked list dynamically – each node is created as needed —Nodes of linked lists are not necessarily stored contiguously in memory (unlike an array). —Although lists of data can be stored in arrays, linked lists provide several advantages.—

Advantages of Linked List

Dynamic: —A linked list is appropriate when the number of data elements to be stored in the list is unknown. —Because linked lists are dynamic, their size can grow or shrink to accommodate the actual number of elements in the list. —The size of a “conventional” C++ array, however, cannot be altered, because the array size is fixed at compile time. —Also, arrays can become full (i.e., all elements of the array are occupied). A linked list is full only when the computer runs out of memory in which to store nodes.

Easy Insertions and Deletions: —Although arrays are easy to implement and use, they can be quite inefficient when sequenced data needs to be inserted or deleted. —With arrays, it is difficult to rearrange data (copying to temporary variables, etc.) —However, the linked list structure allows us to easily insert and delete items from a list. —For example, we can perform efficient searches on arrays (e.g., binary search) but this is not practical with a linked list.

—Linked list object holds a reference to the first node on the list. Each node object consists of data fields, storing the data, and a link field that references to the next node in the list

—One of the attributes of a linked list is that there is not a physical relationship between the nodes; that is, they are not stored contiguously in memory (as array elements are). —

To determine the beginning of the list, and each additional element in the list, we need to use pointers. —The pointer to the first node in the list is referred to as the head pointer, because it points to the head node in the list. —In addition to the head pointer, there are usually other pointers associated with the list. These can include a pointer to the last element in the list (tail pointer) and a pointer that traverses the list to find data (navigator or traversal pointer). —Oftentimes it is convenient to create a structure that contains the head pointer of a list and also information about the list itself (e.g., number of elements currently in the list, maximum number of elements to be allowed in the list, etc).

—This extra data is referred to as metadata.

—Abstract Implementation

—A linked list is usually implemented with 2 classes/Structures:

  • List class
  • Node class

—The Node class will contain the data and link fields. —The List class will contain the head pointer and the metadata, along with the list insert and delete functions.

Operations

—With a linked list, there are a standard set of functions that operate on the list:

  • Creating the list
    • Initialize pointers to NULL;
  • Inserting nodes
    • Insert at beginning
    • Insert at middle
    • Insert at last
  • Deleting nodes
    • Delete from beginning, middle, last
  • Traversing the list
  • Destroying the list

Sample program

—We will create dynamic list of persons. —User can enter data of as many persons as he wants, can add persons at rear, front. User can delete persons at rear, can view contents of list any time.

#include <iostream>
#include <conio.h>
struct person {
		char name[25];
		int age;
		struct person *Next_Person;
};
struct linkedlist {
	struct person *head;
	struct person *tail;
	int nodeCount;
};
void initialize (linkedlist *ll);
void InsertFront (linkedlist *ll);
void InsertRear (linkedlist *ll);
void DeleteRear (linkedlist *ll);
void setData (person *p);
void PrintList (linkedlist *ll);

void main ()
{
	linkedlist ll; //linked list created
	initialize(&ll); //linked list initialized
	int choice = 0;
	//list is empty, lets create person //dynamically
	do
     {
	cout << " 1: insert item in front" << endl;
	cout << " 2: Insert item in rear" << endl;
	cout << " 3: Delete item from front" << endl;
	cout << " 4: Delete item from rear" << endl;
	cout << " 5: Print List" << endl;
	cout << " 8: Exit" << endl;
	cin >> choice;
if (choice == 1)
{   InsertFront(&ll);	}

if (choice == 2)
{   InsertRear(&ll);	}

if (choice == 3)
{//	DeleteFront(&ll);  }

if (choice == 4)
{   DeleteRear(&ll);	}

if (choice == 5)
{   PrintList(&ll);    }

}while (choice != 8);
}

void initialize(linkedlist *ll)
{
	ll->head = NULL;
	ll->tail = NULL;
	ll->nodeCount = 0;
}

void setData(person *p)
{
		cin >> p->name ;
		cin >> p->age ;
		p->Next_Person = NULL;	//just to initialize
}

void InsertFront(linkedlist *ll)
{
	if (ll->head == NULL && ll->nodeCount == 0) //means empty list
	{
		person *p;
		p = new person;
		setData(p);
		ll->head = p;
		ll->tail = p;
		ll->nodeCount++;
	}
	else
	{
		person *p;
		p = new person;
		setData(p);
		p->Next_Person = ll->head ;
		ll->head = p;
		ll->nodeCount++; //increment counter
	}
}

void InsertRear(linkedlist *ll)
{
	if (ll->head == NULL && ll->nodeCount == 0) //means empty list
	{
		person *p;
		p = new person;
		setData(p);
		ll->head = p;
		ll->tail = p;
		ll->nodeCount++;
	}
	else
	{
		person *p;
		p = new person;
		setData(p);

		ll->tail->Next_Person  = p;    //now point tail of second last element to last
		ll->tail = p;   //yes tail is now the new element inserted
		ll->nodeCount++;    //increment counter
	}
}

void DeleteRear(linkedlist *ll)
{
	person *tempLast;
	person *temp2ndLast;
	tempLast = ll->head ;
	if (ll->nodeCount > 0 )
	{	//we can use for loop with nodeCount or the following method
		while (tempLast->Next_Person != NULL)
		{
			temp2ndLast = tempLast;
			tempLast = tempLast->Next_Person ;
		}
		temp2ndLast->Next_Person = NULL;
		delete tempLast;
		ll->nodeCount --;
	}
}

void PrintList(linkedlist *ll)
{
	int i = 0;
	struct person *tempNode;
	tempNode = ll->head ;
	cout << "The linked list is..." << endl;
	for (i = 0; i < ll->nodeCount ; i++)
	{
		cout << tempNode->name <<"\t" <<tempNode->age << endl; ;
		tempNode = tempNode->Next_Person ;
	}
}

Explanation

Linked list starts with the initialize function.

void initialize(linkedlist *ll)

When we add an Item to an Empty Linked List, we’ll make both head and tail point at the new node, and increment the list’s size.

Insert Item at the Front (non-empty list) requires following steps:

  • Create a new node
  • Make the new node point at the current front node
  • Reset head so that it points at the new node, and increment size of the linked list

Insert at Rear also requires the same steps:

  • Build the new node
  • Make the current tail node point to the new node
  • Reset tail so that it points to the new node, and increment the list size

To remove Last Item From a Linked List

  • Set the link reference in the previous node to NULL, make tail point at this node, and decrement the list size
  • Save a reference to the removed data object and get rid of the removed node object

To remove the Only Item From a Linked List

  • Save a reference to the node
  • Set head and tail to NULL, and decrement the size of the list
  • Get rid of the node

Traversing a linked list

—Algorithms that traverse a list start at the first node and examine each node in succession until the last node has been processed. —Traversal logic is used by several different types of algorithms, such as

  • Changing a value in each node,
  • Printing the list,
  • Summing a field in the list,
  • or Calculating the average of a field and etc…

—Any application that requires that the entire list be processed uses the traversal. —To traverse the list we need a walking (navigator/traversal) pointer. This pointer is used to move from node to node as each element is processed. Example is our print function in the linked list example code above.

Doubly Linked List

There are two problems with Singly Linked Lists. One we can’t get back to the beginning of the list from the end. Second, we can’t go backwards through the list. Therefore, doubly linked lists and circular linked lists were invented.

Tagged with: C/C++ languageData structures
 

One Response to Linked lists in C++

  1. Faizan says:

    In delete rear function at end after deleting the “templast node”.
    Don’t you think that the tail of the link list should now point to “temp2ndlast node” ? Because tail always points to the last node.
    And temp2ndlast is the last node.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.