Introduction to Linked Lists

A Dynamic Memory Allocation Method

That is a Combination of:

struct data types

that incorporate pointer variables

use of new and delete operators

Struct Syntax

struct newstruct

{
int first;
float second;
char third;
int fourth [10];
};

Modified Struct Syntax

For Dynamic Memory Allocation

struct newstruct

{
int first;
float second;
char third;
int fourth [10];
newstruct * next;
};

Declaration and Use of pointer variable

Syntax

int * ptr;

Reserves memory for a variable that can have a memory address of an int as its set of allowed values (and NULL).

newstruct * struct_ptr;

Reserves memory for a variable that can have a memory address of a block of memory of type newstruct as its set of allowed values (and NULL).

Review of various symbols used in Linked Lists

* declaring a pointer variable
* dereferencing operator - value at pointer variable's address

-> alternate form of dereferencing operator

(* struct_ptr). fourth[3] = 14; is equivalent to
struct_ptr -> fourth[3] = 14;

Building Linked Lists

Uses the Following Processes:

Dynamically allocating memory for a structure - create a struct

Populating the structure with suitable data values

Incorporating the structure into a linked list organization of the data

Linked List Program

#include < iostream >
#include < fstream >
using namespace std;

/* This program contains a set of linked list functions and that can be used for operations on linked lists.
This program needs a simple textfile that contains a coded character, an integer and a floating point value
in single lines. Many lines can be provided. The program contains functions that build, delete and modify elements of linked lists of structures. These functions are essentially those developed as examples in class. */

struct std_struct
{
int firstmember;
float secondmember;
std_struct *next;
};

// Function Prototypes std_struct * buildum (ifstream &, std_struct );
int writeall (std_struct );
int empty (std_struct );
std_struct insert_at_front ( std_struct , std_struct );
std_struct * insert_at_end (std_struct , std_struct );
std_struct * insert_in_order (std_struct , std_struct );
std_struct * create ( );
std_struct * populate (std_struct * temp, int number, ifstream & datain);
std_struct * delete_last (std_struct );
std_struct search (std_struct , int);
std_struct delete_first (std_struct );
std_struct delete_specific (std_struct *, int);

int main ()
{
std_struct head, current, *previous;
int number = 0, counter = 0, id;
ifstream myinput;

head = NULL;
head = buildum (myinput, head);
counter = writeall (head);
cout << endl <<"There are " << counter << " elements in the linked list"
<< endl << endl;
id = 4;
previous = search (head, id);
counter = writeall (previous);
cout << endl <<"There are " << counter << " elements in the linked list" << endl;
return 0;
}

int writeall (std_struct *current)

/* Writeall displays the members of each element of the linked list of structures of type std_struct
pointed to by its pointer variable argument (current). It displays the values to the output stream.
Writeall returns the number of elements displayed */

{
int counter = 0; // counter counts the # displayed

while (current != NULL)
{
cout << "firstmember's value is: " << current->firstmember
<< " secondmember's value is: " << current->secondmember << endl;
counter++;
current = current->next;
}
cout << endl;
return counter;
}

std_struct * buildum (ifstream & datain, std_struct *current)

/* Buildum uses the default input stream to obtain values for the execution of the program.
It accepts 3 building orders identified by the first character in the stream
(f for front, e for end, and i for inorder) to determine the building order of the linked list.
It then accepts all pairs of values in the stream (int and a float) and builds a linked list in the order required. */

{
int number; char insert_type; std_struct *temp; datain.open ("buildll.dat");

datain >> insert_type; datain >> number;
while (!datain.eof())
{
temp = create ( );
temp = populate (temp, number, datain);
if (insert_type == 'f') current = insert_at_front (current, temp);
else if (insert_type == 'e') current = insert_at_end (current, temp);
else if (insert_type == 'i') current = insert_in_order (current, temp);
datain >> number;
} ;
datain.close ();
return current;
}

std_struct * create ( )

{
std_struct * temp;
temp = new std_struct;
temp -> next = NULL;
return temp;
}

std_struct * populate (std_struct * temp, int number, ifstream & datain)

/* Function Populate provides data to the member variables of the structure pointed to by it's first parameter. The second parameter is used as the value for the member variable firstmember and the third parameter is used to extract the data value from the file for the secondmember variable. The function returns the pointer to the structure that is now populated (has values for the member variables). */

{
temp->firstmember = number;
datain >> (temp->secondmember);
return temp;
}

int empty (std_struct *temp)

/* empty tests its pointer variable parameter, temp,
for NULL and returns the integer value of the result of the test */

{
return (temp == NULL);
}

std_struct * insert_at_front (std_struct current, std_struct newitem)

/* insert_at_front inserts the record pointed to by its second parameter newitem in the begining of the
linked list pointed to by its first parameter, parameter, current. Note that the values of the fields for
the record pointed to by newitem have been initialized before the call to insert_at_front. */

{
std_struct *temp;

temp = current;
if (empty (temp)) current = newitem;
else
{
newitem->next = temp;
current = newitem;
};
return current;
}

std_struct * insert_at_end (std_struct head, std_struct newitem)

/* insert_at_end inserts the record pointed to by its second parameter, newitem, at the end of the linked list
pointed to by its first parameter, head. Note that the values of the fields for the record pointed to by newitem
have been initialized before the call to insert_at_end. The function returns the pointer to the linked list of
elements with the new element inserted. */

{
std_struct *current;

current = head;
if (empty (current)) head = newitem;

else
{
while (current->next != NULL)
current = current->next;

current->next = newitem;
}
return head;
}

std_struct * insert_in_order (std_struct *head, std_struct *newitem)

/* insert_in_order inserts the record pointed to by its second parameter, newitem, into the list
pointed to by its first parameter, head. It maintains the list's lowest to highest order of the firstmember.
insert_in_order returns the pointer to the first element of the linked list with the new element inserted in order. */

{
std_struct * current, * dummy;

current = head;
if (empty (current)) current = insert_at_front (head, newitem);
else if (newitem->firstmember <= current->firstmember)
current = insert_at_front (head, newitem);

else
{
dummy = create ();
dummy -> next = newitem -> next;
dummy -> firstmember = newitem -> firstmember;
current = insert_at_end (head, dummy);
while ( newitem->firstmember > current->next->firstmember)
current = current->next;

newitem->next = current->next;
current->next = newitem;
current = head;
current = delete_last (head);
}
return current;
}

std_struct * delete_first (std_struct *current)

/* delete_first deletes the first element of the list pointed to by its parameter, current.
delete_first returns the pointer to the linked list of elements with the first element removed */

{
std_struct *temp;

temp = current;
if (empty (temp)) temp = NULL;
else if (temp->next == NULL)
{
delete temp;
temp = NULL;
}
else
{
current = temp->next;

delete temp;
temp = current;
}
return temp;
}

std_struct * delete_last (std_struct *head)

/* delete_last deletes the last element of the list pointed to by its parameter, head.
delete_last returns the pointer to the linked list of elements with the last element removed */

{
std_struct *current;

current = head;
if (empty (current)) current = NULL;
else if (current->next == NULL)
{
delete current;
current = NULL;
}
else
{
while (current->next->next != NULL)
current = current->next;

delete current->next;
current->next = NULL;
current = head;
}
return current;
}

std_struct * search (std_struct * head, int id)

/* search traverses the linked list pointed to by its first parameter ( head)
until it locates an element that matches the value of its second parameter (id).
search returns the pointer to the matched element of the linked list or null if the match fails.
search inserts a dummy element to facilitate the traversal process. */

{
std_struct * temp, * current;

current = head;
temp = new std_struct;
temp -> next = NULL; temp -> firstmember = id;
temp -> secondmember = -99.99;
current = insert_at_end (current, temp);
while (current->firstmember != id) current = current->next;

if ( current -> next == NULL)
{
current = head;
delete_last (current);
return NULL;
}
else
{
temp = current;
current = head;
delete_last (current);
return temp;
}
}

std_struct * delete_specific (std_struct * head, int number);

{
return head;

}

Introduction to Linked Lists

A Dynamic Memory Allocation Method

That is a Combination of: struct data types that incorporate pointer variables use of new and delete operators

Struct Syntax

struct newstruct { int first; float second; char third; int fourth [10]; };

Modified Struct Syntax

For Dynamic Memory Allocation

struct newstruct { int first; float second; char third; int fourth [10]; newstruct * next; };

Declaration and Use of pointer variable

Building Linked Lists

Uses the Following Processes:

Dynamically allocating memory for a structure - create a struct Populating the structure with suitable data values Incorporating the structure into a linked list organization of the data

Linked List Program

#include < iostream > #include < fstream > using namespace std;

struct std_struct { int firstmember; float secondmember; std_struct *next; };

int writeall (std_struct *current)

/* Writeall displays the members of each element of the linked list of structures of type std_struct pointed to by its pointer variable argument (current). It displays the values to the output stream. Writeall returns the number of elements displayed */

{ int counter = 0; // counter counts the # displayed while (current != NULL) { cout << "firstmember's value is: " << current->firstmember << " secondmember's value is: " << current->secondmember << endl; counter++; current = current->next; } cout << endl; return counter; }

std_struct * buildum (ifstream & datain, std_struct *current)

std_struct * create ( )

std_struct * populate (std_struct * temp, int number, ifstream & datain)

int empty (std_struct *temp)

/* empty tests its pointer variable parameter, temp, for NULL and returns the integer value of the result of the test */

std_struct * insert_at_front (std_struct *current, std_struct *newitem)

std_struct * insert_at_end (std_struct *head, std_struct *newitem)