Intuition and Example for Linked Lists
Consider a situation where we have an array that stores letters. Along with each letter, we store the position of the next letter in alphabetical order. We store these two pieces of information (the letter and index of the next letter) in a struct:
struct Node {
char data;
int next;
};
Assume we have the array
shownat right:
Consider the following code used to insert the letter ‘b’ in ascending alphabetical order:
Issues in doing this are that we want our code to work in general for any letter. We also have the restriction above in that we can store at most 10 letters. We can use the new command to dynamically allocate memory for a node (that would later be deallocated using delete.) In C we would use malloc to allocate memory and free to deallocate it.
struct Node {
char data;
Node *pNext;
};
Consider the code needed to create:
See the next page for a sample program to add numbers to a list, though not in order.
/* listprog1.cpp - Demo program to illustrate linked lists
*/
#include <iostream>
using namespace std;
struct Node {
int data; // The data being stored at the node
Node *pNext; // Pointer to the next node
};
void displayList( Node *pHead)
{
Node *pTemp= pHead; /* Used to traverse list without destroying head*/
cout < "\nJust entered Fcn. displayList...";
while( pTemp != NULL) {
cout < pTemp->data < " ";
pTemp = pTemp->pNext;
}
cout < "\n\n";
}
int processNumbers( Node *head, int operation)
{
Node *pTemp = head;
int result = 0; // stores the calculated answer
if (operation == 2) // Multiply was the action chosen
result = 1;
while (pTemp != NULL) { // Go through list, doing the operation
if (operation == 1) // Add was the action chosen
result += pTemp->data;
else if (operation == 2) // Multiply was the action chosen
result *= pTemp->data;
pTemp = pTemp->pNext; // Advance to next list member
}
return result;
}
int main()
{
int number = 0; // Used to store numbers read in
Node *head = NULL; // head of linked list
Node *pTemp; // used in new node creation
int menuChoice; // Menu choice
int answer; // Answer of chosen operation
cout < "This program finds sum or product of a variable number \n";
cout < " of integers. Enter as many integers > 0 as you would like \n";
cout < " followed by the value -1.\n\n";
cout < "The numbers are: ";
while ( number != -1) {
cin > number;
if (number != -1) {
pTemp = new Node;
// Insert at head of list
pTemp->data = number;
pTemp->pNext = head;
head = pTemp;
}
}
displayList( head);
cout < "Please select the number of one of these options: \n";
cout < " 1. Sum the numbers in the list\n";
cout < " 2. Multiply the numbers in the list \n";
cout < " 3. Exit the program.\n";
cout < "Your choice: ";
cin > menuChoice;
if (menuChoice == 3)
exit( 0);
answer = processNumbers( head, menuChoice);
cout < "Answer is: " < answer < endl;
system("pause"); // stop output screen from disappearing in DevC++
return 0; // return value to keep C++ happy
}