Linked Lists in C++

Linked Lists

Overview of Lists Introduction A linked list is a technique of creating a list with the ability to add, delete, or retrieve items. Additional operations can also be provided to a more elaborate list such as finding an item, deleting an item, etc. The Items of a List Before creating a list, you probably should first decide or define what the list would be made of. As different as they are, one list can be made of numbers. Another list may be made of strings. Yet another could be made of simple Boolean values. The item(s) that will compose the list should be created in a separate class, usually a structure (simply because the member(s) of a struct, as compared to a class, is(are) automatically made public). For example, a list that will be made of numbers can define the item's class as follows: struct Items{ double Number;}; You may want a list that is made of names. Such a list can be created from a class that includes a string member variable like an array of chars. Another type of list can contain complex objects. For example, if you are starting a database for a car part dealer, you may want to create a list that includes information about car parts. The class that holds information for a part can be created as follows: struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice;}; Implementing a Linked List Introduction After deciding what each item of the list would be made of, you can create a class that would manage the list. This class would be responsible for all operations that can be performed on the list. Here is an example: Header File: ListOfParts.h #pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice;};//---------------------------------------------------------------------------class ListOfParts{public: ListOfParts();};//--------------------------------------------------------------------------- Source File: ListOfParts.cpp #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts(){}//--------------------------------------------------------------------------- It is commonly a good practice to include in a class' list a member that can be used to keep track of the number of items in the list. You can declare such a member variable as public but because it is a regular member variable, it is also a habit of OOP developers to make such a member private. If you do this and if you want the value to be accessed outside, you should then provide a public method that serves as the entry point. Here is how this can be done: Header File: ListOfParts.h #pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice;};//---------------------------------------------------------------------------class ListOfParts{private: int size;public: ListOfParts(); int Count();};//--------------------------------------------------------------------------- Source File: ListOfParts.cpp #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts() : size(0){}//---------------------------------------------------------------------------int ListOfParts::Count(){ return size;}//--------------------------------------------------------------------------- Source File: Exercise.cpp #include #include "ListOfParts.h"using namespace std;//---------------------------------------------------------------------------int main(){ ListOfParts *Parts = new ListOfParts(); cout << "Number of Parts: " << Parts->Count() <<> This would produce: Number of Parts: 0

The Beginning of a Linked List

If you create an array-based list, you can start by declaring an array member variable that would hold the items and each item can be located by an index that is assigned to it when the item is added to the list. When you do this, you must provide an estimate of the maximum number of items that will be allowed in the list. Without good planning, the dimension you specify could be too high or too low but C++ doesn't allow you to declare an array without a dimension if you are not initializing the array. This means that, when you create an array-based list, you must also specify the maximum number of items that the list can hold. A linked list is a list that can grow or shrink as the user wishes. This means that, when creating the list, you don't need to predict the maximum number of items that will be added to the list. To use this flexibility, the items must be managed through pointers. Because the list would use a member that defines its item, you can declare a member variable that is conform to the intended items. When a list starts, it is empty or at least it must be considered like that, before any item is added to it. To specify this, you should declare a primary member variable. Although you can call it anything, it is usually called Head. This member can be made private if you don't intend to access it outside of the class. If you want clients of the class to access it, you can make it public. Although this member is declared as a pointer and it marks the beginning of the list, you should not allocate memory for it in the constructor. Its memory would be managed when it is accessed. Therefore, you can simply initialize is as NULL. Here is an example:

Header File: ListOfParts.h

#pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice;};//---------------------------------------------------------------------------class ListOfParts{private: int size;public: ListOfParts(); int Count(); CarPart* Head;};//---------------------------------------------------------------------------

Source File: ListOfParts.cpp

#include #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts() : size(0), Head(NULL){}//---------------------------------------------------------------------------int ListOfParts::Count(){ return size;}//---------------------------------------------------------------------------

The Linking of a List

As mentioned already, each member of an array-based list can be accessed using its index, stored in an item member variable declared as an array. Because the items of a linked list are not indexed, you must provide another mechanism to locate an item in the list. The easiest way to do this is to first locate an item, then ask that item to provide you with a pointer to the item that succeeds it. If the list is empty, this information would be provided as null. If the item you first access is the last in the list, you would also provide nothing. Any other item in the middle would give you access to the next item in the list. To support this theory, you must provide a pointer to the next item in the list as a member variable to the class that holds the item. As a tradition, this member variable is called Next but you can give it any name you want. Because this item actually is a complete one, it must be declared as a self-referencing member that has the same name as its class:

Header File: ListOfParts.h

#pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice; CarPart* Next;};//---------------------------------------------------------------------------class ListOfParts{private: int size;public: ListOfParts(); int Count(); CarPart* Head;};//---------------------------------------------------------------------------

Operations of a Linked List

Item Addition

The primary operation you can perform on a list is to add a new item to it, since a list is fundamentally empty when it starts. In order to indicate that you want to add an item to the list, you can declare a method that receives an item as argument. For the return type, you have two main options. Because the main job of this method is to add a new item, which it hardly fails to do if you implement it right, it can be defined as void. Alternatively, you can make it return the position of the new item in the list. Here is an example:

Header File: ListOfParts.h

#pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice; CarPart* Next;};//---------------------------------------------------------------------------class ListOfParts{private: int size;// List Builderpublic: ListOfParts(); int Count(); CarPart* Head;// List Operationspublic: int Add(CarPart* Item);};//---------------------------------------------------------------------------

Source File: ListOfParts.cpp

#include #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts() : size(0), Head(NULL){}//---------------------------------------------------------------------------int ListOfParts::Count(){ return size;}//---------------------------------------------------------------------------int ListOfParts::Add(CarPart *NewItem){ CarPart *Sample = new CarPart; Sample = NewItem; Sample->Next = Head; Head = Sample; return size++;}//---------------------------------------------------------------------------

Source File: Exercise.cpp

#include #include "ListOfParts.h"using namespace std;//---------------------------------------------------------------------------int main(){ ListOfParts *Parts = new ListOfParts(); CarPart *Part; Part = new CarPart; Part->PartNumber = 9743; strcpy(Part->PartName, "Air Filter"); Part->UnitPrice = 8.75; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27487; strcpy(Part->PartName, "Clutch Disk"); Part->UnitPrice = 47.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 87873; strcpy(Part->PartName, "Brake Disk"); Part->UnitPrice = 35.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27644; strcpy(Part->PartName, "A/C Filter Drier"); Part->UnitPrice = 55.55; Parts->Add(Part); cout << "Number of Parts: " <<>Count() <<>

Item Retrieval

Once a list exists, the user can explorer it. One of the operations performed on items is to locate and retrieve one. To do this, you can declare a method that takes as argument as index. The method would examine the argument with regards to the number of items in the list to make sure the argument's value is in the range of current items of the list. If the number is too low or too high, the method can return null or 0. If the number is in the range, the method can return the item at that position. Here is an example:

Header File: ListOfParts.h

#pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice; CarPart* Next;};//---------------------------------------------------------------------------class ListOfParts{private: int size;// List Builderpublic: ListOfParts(); int Count(); CarPart* Head;// List Operationspublic: int Add(CarPart* Item); CarPart *Retrieve(int pos);};//---------------------------------------------------------------------------

Source File: ListOfParts.cpp

#include #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts() : size(0), Head(NULL){}//---------------------------------------------------------------------------int ListOfParts::Count(){ return size;}//---------------------------------------------------------------------------int ListOfParts::Add(CarPart *NewItem){ CarPart *Sample = new CarPart; Sample = NewItem; Sample->Next = Head; Head = Sample; return size++;}//---------------------------------------------------------------------------CarPart *ListOfParts::Retrieve(int Position){ CarPart *Current = Head; for(int i = Count() - 1; i > Position && Current != NULL; i--) { Current = Current->Next; } return Current;}//---------------------------------------------------------------------------

Source File: Exercise.cpp

#include #include "ListOfParts.h"using namespace std;//---------------------------------------------------------------------------int main(){ ListOfParts *Parts = new ListOfParts(); CarPart *Part; Part = new CarPart; Part->PartNumber = 9743; strcpy(Part->PartName, "Air Filter"); Part->UnitPrice = 8.75; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27487; strcpy(Part->PartName, "Clutch Disk"); Part->UnitPrice = 47.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 87873; strcpy(Part->PartName, "Brake Disk"); Part->UnitPrice = 35.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27644; strcpy(Part->PartName, "A/C Filter Drier"); Part->UnitPrice = 55.55; Parts->Add(Part); cout << "Number of Parts: " <<>Count() << color="#ff0000">for(int i = 0; i <>Count(); i++) { CarPart* One = Parts->Retrieve(i); cout << "\nCar Part Information"; cout << "\nPart #: " <<>PartNumber; cout << "\nDescription: " <<>PartName; cout << "\nUnit Price: $" <<>UnitPrice <<> cout <<>

This would produce: Number of Parts: 4Car Part InformationPart #: 27644Description: A/C Filter DrierUnit Price: $55.55Car Part InformationPart #: 87873Description: Brake DiskUnit Price: $35.15Car Part InformationPart #: 27487Description: Clutch DiskUnit Price: $47.15Car Part InformationPart #: 9743Description: Air FilterUnit Price: $8.75

Item Deletion

Deleting an item consists of removing it from the list. There are two main types of deletion you can perform on a list. You can simply ask the class to delete an item. In this case, it is usually the item at the end that gets deleted. If you do this, make sure you perform other routines operations such as decrementing the count of items in the list. Here is an example:

Header File: ListOfParts.h

#pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice; CarPart* Next;};//---------------------------------------------------------------------------class ListOfParts{private: int size;// List Builderpublic: ListOfParts(); int Count(); CarPart* Head;// List Operationspublic: int Add(CarPart* Item); CarPart *Retrieve(int pos); bool Delete();};//---------------------------------------------------------------------------

Source File: ListOfParts.cpp

#include #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts() : size(0), Head(NULL){}//---------------------------------------------------------------------------int ListOfParts::Count(){ return size;}//---------------------------------------------------------------------------int ListOfParts::Add(CarPart *NewItem){ CarPart *Sample = new CarPart; Sample = NewItem; Sample->Next = Head; Head = Sample; return size++;}//---------------------------------------------------------------------------CarPart *ListOfParts::Retrieve(int Position){ CarPart *Current = Head; for(int i = 0; i < current =" Current-">Next; } return Current;}//---------------------------------------------------------------------------bool ListOfParts::Delete(){ if( Head == NULL ) { std::cout << "The list is empty\n"; return false; } else { CarPart *Current; Current = Head->Next; Head->Next = Current->Next; size--; return true; }}//---------------------------------------------------------------------------

Source File: Exercise.cpp

#include #include "ListOfParts.h"using namespace std;//---------------------------------------------------------------------------int main(){ ListOfParts *Parts = new ListOfParts(); CarPart *Part; // Visual C++ 6 can't "scope" a variable in a for loop int i; Part = new CarPart; Part->PartNumber = 9743; strcpy(Part->PartName, "Air Filter"); Part->UnitPrice = 8.75; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27487; strcpy(Part->PartName, "Clutch Disk"); Part->UnitPrice = 47.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 87873; strcpy(Part->PartName, "Brake Disk"); Part->UnitPrice = 35.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27644; strcpy(Part->PartName, "A/C Filter Drier"); Part->UnitPrice = 55.55; Parts->Add(Part); cout << "Number of Parts: " <<>Count() << i =" 0;">Count(); i++) { CarPart* One = Parts->Retrieve(i); cout << "\nCar Part Information"; cout << "\nPart #: " <<>PartNumber; cout << "\nDescription: " <<>PartName; cout << "\nUnit Price: $" <<>UnitPrice << color="#ff0000">Parts->Delete(); cout << "\nNumber of Parts: " <<>Count() << i =" 0;">Count(); i++) { CarPart* One = Parts->Retrieve(i); cout << "\nCar Part Information"; cout << "\nPart #: " <<>PartNumber; cout << "\nDescription: " <<>PartName; cout << "\nUnit Price: $" <<>UnitPrice <<>

This would produce: Number of Parts: 4-=- List of Parts -=-Car Part InformationPart #: 27644Description: A/C Filter DrierUnit Price: $55.55Car Part InformationPart #: 87873Description: Brake DiskUnit Price: $35.15Car Part InformationPart #: 27487Description: Clutch DiskUnit Price: $47.15Car Part InformationPart #: 9743Description: Air FilterUnit Price: $8.75Number of Parts: 3-=- List of Parts -=-Car Part InformationPart #: 27644Description: A/C Filter DrierUnit Price: $55.55Car Part InformationPart #: 27487Description: Clutch DiskUnit Price: $47.15Car Part InformationPart #: 9743Description: Air FilterUnit Price: $8.75Press any key to continue Another technique used to delete an item consists of specifying the position of the item to be deleted. To do this, you can pass an argument as the desired position. The method would check the range of values of the current list. If the specified position is beyond the appropriate range, the method can return false, 0, or null, depending on how you create it. Here is an example:

Header File: ListOfParts.h

#pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice; CarPart* Next;};//---------------------------------------------------------------------------class ListOfParts{private: int size;// List Builderpublic: ListOfParts(); int Count(); CarPart* Head;// List Operationspublic: int Add(CarPart* Item); CarPart *Retrieve(int pos); bool Delete(); bool Delete(int pos);};//---------------------------------------------------------------------------

Source File: ListOfParts.cpp

#include #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts() : size(0), Head(NULL){}//---------------------------------------------------------------------------int ListOfParts::Count(){ return size;}//---------------------------------------------------------------------------int ListOfParts::Add(CarPart *NewItem){ CarPart *Sample = new CarPart; Sample = NewItem; Sample->Next = Head; Head = Sample; return size++;}//---------------------------------------------------------------------------CarPart *ListOfParts::Retrieve(int Position){ CarPart *Current = Head; for(int i = 0; i < current =" Current-">Next; } return Current;}//---------------------------------------------------------------------------bool ListOfParts::Delete(){ if( Head == NULL ) { std::cout << "The list is empty\n"; return false; } else { CarPart *Current; Current = Head->Next; Head->Next = Current->Next; size--; return true; }}//---------------------------------------------------------------------------bool ListOfParts::Delete(int Position){ if( Retrieve(Position) == NULL ) return false; else { Retrieve(Position - 1)->Next = Retrieve(Position+1); size--; return true; }}//---------------------------------------------------------------------------

Source File: Exercise.cpp

#include #include "ListOfParts.h"using namespace std;//---------------------------------------------------------------------------int main(){ ListOfParts *Parts = new ListOfParts(); CarPart *Part; // Visual C++ 6 can't "scope" a variable in a for loop int i; Part = new CarPart; Part->PartNumber = 9743; strcpy(Part->PartName, "Air Filter"); Part->UnitPrice = 8.75; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27487; strcpy(Part->PartName, "Clutch Disk"); Part->UnitPrice = 47.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 87873; strcpy(Part->PartName, "Brake Disk"); Part->UnitPrice = 35.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27644; strcpy(Part->PartName, "A/C Filter Drier"); Part->UnitPrice = 55.55; Parts->Add(Part); cout << "Number of Parts: " <<>Count() << i =" 0;">Count(); i++) { CarPart* One = Parts->Retrieve(i); cout << "\nCar Part Information"; cout << "\nPart #: " <<>PartNumber; cout << "\nDescription: " <<>PartName; cout << "\nUnit Price: $" <<>UnitPrice << color="#ff0000">Parts->Delete(2); cout << "\nNumber of Parts: " <<>Count() << i =" 0;">Count(); i++) { CarPart* One = Parts->Retrieve(i); cout << "\nCar Part Information"; cout << "\nPart #: " <<>PartNumber; cout << "\nDescription: " <<>PartName; cout << "\nUnit Price: $" <<>UnitPrice <<>

This would produce: Number of Parts: 4-=- List of Parts -=-Car Part InformationPart #: 27644Description: A/C Filter DrierUnit Price: $55.55Car Part InformationPart #: 87873Description: Brake DiskUnit Price: $35.15Car Part InformationPart #: 27487Description: Clutch DiskUnit Price: $47.15Car Part InformationPart #: 9743Description: Air FilterUnit Price: $8.75Number of Parts: 3-=- List of Parts -=-Car Part InformationPart #: 27644Description: A/C Filter DrierUnit Price: $55.55Car Part InformationPart #: 87873Description: Brake DiskUnit Price: $35.15Car Part InformationPart #: 9743Description: Air FilterUnit Price: $8.75Press any key to continue

Item Location

One of the operations hardly performed on a list is to find one. This is because if you ask a list to locate a particular item, you must provide as much information as possible. Probably the most expedient way you can do this is to completely define an item and pass it to the list. Only if the item is found in the list would it be recognized. In the source code, we implement this method as Find().

There are different ways you can try locating an item in a list. For example, you can provide partial information and try locating all items that match such an entry. Here is an example:

Linked List Source Code

Header File: ListOfParts.h

#pragma once//---------------------------------------------------------------------------struct CarPart{ long PartNumber; char PartName[40]; double UnitPrice; CarPart* Next;};//---------------------------------------------------------------------------class ListOfParts{private: int size;// List Builderpublic: ListOfParts(); int Count(); CarPart* Head;// List Operationspublic: int Add(CarPart* Item); CarPart *Retrieve(int pos); bool Delete(); bool Delete(int pos); bool Find(CarPart* Item);};//---------------------------------------------------------------------------

Source File: ListOfParts.cpp

#include #include "ListOfParts.h"//---------------------------------------------------------------------------ListOfParts::ListOfParts() : size(0), Head(NULL){}//---------------------------------------------------------------------------int ListOfParts::Count(){ return size;}//---------------------------------------------------------------------------int ListOfParts::Add(CarPart *NewItem){ CarPart *Sample = new CarPart; Sample = NewItem; Sample->Next = Head; Head = Sample; return size++;}//---------------------------------------------------------------------------CarPart *ListOfParts::Retrieve(int Position){ CarPart *Current = Head; for(int i = 0; i < current =" Current-">Next; } return Current;}//---------------------------------------------------------------------------bool ListOfParts::Delete(){ if( Head == NULL ) { std::cout << "The list is empty\n"; return false; } else { CarPart *Current; Current = Head->Next; Head->Next = Current->Next; size--; return true; }}//---------------------------------------------------------------------------bool ListOfParts::Delete(int Position){ if( Retrieve(Position) == NULL ) return false; else { Retrieve(Position - 1)->Next = Retrieve(Position+1); size--; return true; }}//---------------------------------------------------------------------------bool ListOfParts::Find(CarPart* ItemToFind){ CarPart *Current; if( ItemToFind == NULL ) return false; for(Current = Head; Current != NULL; Current = Current->Next) { if( (Current->PartNumber == ItemToFind->PartNumber) && (strcmp(Current->PartName, ItemToFind->PartName) == 0) && (Current->UnitPrice == ItemToFind->UnitPrice) ) return true; else Current->Next; } return false;}//---------------------------------------------------------------------------

Source File: Exercise.cpp

#include #include "ListOfParts.h"using namespace std;//---------------------------------------------------------------------------int main(){ ListOfParts *Parts = new ListOfParts(); CarPart *Part; CarPart *PartToFind; // Visual C++ 6 can't "scope" a variable in a for loop int i; Part = new CarPart; Part->PartNumber = 9743; strcpy(Part->PartName, "Air Filter"); Part->UnitPrice = 8.75; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27487; strcpy(Part->PartName, "Clutch Disk"); Part->UnitPrice = 47.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 87873; strcpy(Part->PartName, "Brake Disk"); Part->UnitPrice = 35.15; Parts->Add(Part); Part = new CarPart; Part->PartNumber = 27644; strcpy(Part->PartName, "A/C Filter Drier"); Part->UnitPrice = 55.55; Parts->Add(Part); cout << "Number of Parts: " <<>Count() << i =" 0;">Count(); i++) { CarPart* One = Parts->Retrieve(i); cout << "\nCar Part Information"; cout << "\nPart #: " <<>PartNumber; cout << "\nDescription: " <<>PartName; cout << "\nUnit Price: $" <<>UnitPrice << color="#ff0000">PartToFind = new CarPart; PartToFind->PartNumber = 87873; strcpy(PartToFind->PartName, "Brake Disk"); PartToFind->UnitPrice = 35.15; bool Found = Parts->Find(PartToFind); if( Found == true ) cout << "\nItem was found\n"; else cout << "\nItem not found\n"; cout <<>