Linked list
insert "DAT"
delete "CAT"
insert, delete ~ O(1)
STL list
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
#include <stdio.h>
template<class T>
void print_list ( list<T> aList, char *name )
{
list<T>::iterator itr;
cout << name << ": " << endl;
for ( itr = aList.begin(); itr != aList.end(); ++itr ) {
cout << *itr << " ";
}
cout << endl;
}
int main()
{
list <int> list1; //creates an empty list
list1.push_front ( 10 );
list1.push_back ( 20 );
list <int>list2( list1 );
list <string> list3;
list <string *> list4; //list of pointers to strings
list1.swap ( list2 ); //exchange values in list1 and list2
list1.front(); //returns first element ( but does NOT remove )
list1.back(); //returns last element ( but does NOT remove )
//no subscript operator
//need to use iterator to access other elements
list1.push_front ( 10 );
list1.push_back ( 20 );
//same as
list1.insert ( list1.end(), 20 );
list<int>::iterator loc = find( list1.begin(), list1.end(), 8 );
list1.insert ( loc, 7 ); //insert 7 immediately befoe 8
list1.pop_front(); //remove first element
list1.pop_back(); //remove last element
loc = find ( list1.begin(), list1.end(), 18 );
if ( loc != list1.end() )
list1.erase ( loc );
list<int>::iterator start = find( list1.begin(), list1.end(), 8 );
list<int>::iterator stop = find( list1.begin(), list1.end(), 128 );
if ( start != list1.end() )
list1.erase ( start, stop );
list1.remove ( 8 ); //remove all 8s
list1.sort(); //sort in ascending order
list1.reverse(); //reverse list
//erases whole list
list1.erase( list1.begin(), list1.end() );
list2.erase( list2.begin(), list2.end() );
//list1: 1, 2, 3
//list2: 8, 9, 10, 11, 12, 13
list1.push_back( 1 ); list1.push_back( 2 ); list1.push_back( 3 );
list2.push_back( 8 ); list2.push_back( 9 ); list2.push_back( 10 );
list2.push_back( 11 ); list2.push_back( 12 ); list2.push_back( 13 );
print_list( list1, "list1" );
print_list( list2, "list2" );
getchar();
copy( list1.begin(), list1.end(), list2.begin() );
//question: What will be list1, list2 ?
print_list( list1, "list1" );
print_list( list2, "list2" );
getchar();
//insert iterator
copy ( list1.begin(), list1.end(), back_inserter ( list2 ) );
//question: What will be list1, list2 ?
cout << "back_inserter: " << endl;
print_list( list1, "list1" );
print_list( list2, "list2" );
getchar();
//front inserter -- insert at front
cout << "front_inserter: " << endl;
copy ( list1.begin(), list1.end(), front_inserter ( list2 ) );
print_list( list1, "list1" );
print_list( list2, "list2" );
getchar();
//inserter
cout << "inserter:" << endl;
loc = find ( list2.begin(), list2.end(), 12 );
copy ( list1.begin(), list1.end(), inserter( list2, loc ) );
print_list( list1, "list1" );
print_list( list2, "list2" );
getchar();
return 1;
}
|
list.h
//list.h
#ifndef LIST_H
#define LIST_H
template <class T> class link; //forward declaration
template <class T> class listIterator; //forward declaration
template<class T>
class List {
protected:
link<T> *first;
link<T> *last;
public:
//type definition
typedef T value_type;
typedef listIterator<T> iterator;
//constructor and destructor
List ();
virtual ~List();
//operations
bool empty();
int size();
T &front(); //returns first element
T &back(); //returns last element
void push_front ( T & ); //insert from the front
void push_back( T & ); //insert from the back
void pop_front(); //remove first element
void pop_back(); //remove last element
iterator begin();
iterator end();
void sort();
void insert( iterator &, T &);
void erase( iterator & );
void erase( iterator &, iterator &);
};
template <class T>
class listIterator {
typedef listIterator<T> iterator;
protected:
List<T> *theList;
link<T> *currentLink;
friend class List<T>;
public:
//constructor
listIterator ();
listIterator ( List<T> *tl, link<T> *cl );
T &operator * (); //dereferencing
bool operator != ( iterator &rhs );
iterator & operator ++ ( int ); //prefix
iterator operator ++ (); //postfix
};
#endif
|
link.h
|
|
A doubly linked list
list.cpp
//list.cpp
#include <iostream>
#include "list.h"
#include "link.h"
#include <stdio.h>
template<class T>
List<T>::List()
{
first = last = 0; //null list
}
template<class T>
bool List<T>::empty()
{
return first == 0;
}
template<class T>
int List<T>::size()
//count the number of elements in collection
/*
Comments from Tong: This is NOT a good implementation as
it takes time to traverse the list. A better way is to include
a field called 'size' in the List class; when elements are
inserted or deleted, size is adjusted.
*/
{
int count = 0;
link<T> *p;
for ( p = first; p != 0; p = p->next )
count++;
return count;
}
template<class T>
void List<T>::push_front( T &a )
{
link<T> *newLink = new link<T> ( a );
if ( empty() )
first = last = newLink;
else {
first->prev = newLink;
newLink->next = first;
first = newLink;
}
}
template<class T>
void List<T>::pop_front()
{
link <T> *temp = first;
first = first->next;
if ( first != 0 )
first->prev = 0;
else
last = 0;
delete temp;
}
template<class T>
List<T>::~List()
{
link <T> *p = first;
while ( p != 0 ) {
link<T> *temp = p;
p = p->next;
delete temp;
}
}
template<class T>
listIterator<T> List<T>::begin()
{
return iterator ( this, first );
}
template<class T>
listIterator<T> List<T>::end()
{
return iterator ( this, 0 ); //points beyond last
}
//listIterator
//constructors
template<class T>
listIterator<T>::listIterator()
{
}
template<class T>
listIterator<T>::listIterator( List<T> *lp, link<T> *lkp )
{
theList = lp;
currentLink = lkp;
}
template<class T>
T & listIterator<T>::operator * ()
{
return currentLink->value;
}
template<class T>
bool listIterator<T>::operator != ( iterator &rhs )
{
return currentLink != rhs.currentLink;
}
template<class T>
listIterator<T> & listIterator<T>::operator ++ (int)
{
currentLink = currentLink->next;
return *this;
}
template<class T>
listIterator<T> listIterator<T>::operator ++ ()
//postfix form of increment ( e.g. assigned, then increment )
{
//make an old copy
listIterator<T> clone ( theList, currentLink );
currentLink = currentLink->next; //advance pointer
return clone; //return old iterator
}
|
template<class T>
void List<T>::insert( listIterator<T> &itr, T &a )
{
link<T> *p = new link<T> ( a );
link<T> *current = itr.currentLink;
if ( empty() ) { //empty list
first = last = p;
return;
}
//assert ( current );
if ( current == 0 ){ //point to end, thus append to list
last->next = p;
p->next = 0;
p->prev = last;
last = p;
return;
}
//otherwise, always insert before
p->next = current;
p->prev = current->prev;
current->prev = p;
current = p->prev;
if ( current != 0 )
current->next = p;
else
first = p;
}
template<class T>
void List<T>::erase ( listIterator<T> &start, listIterator<T> &stop )
//remove elements from the range ( before stop )
{
link<T> *p = start.currentLink;
link<T> *q = p->prev;
link<T> *stopLink = stop.currentLink;
if ( q == 0 ) { //removing initial portion of list
first = stopLink;
if ( stopLink == 0 ) //pointing to end
last = 0; //whole list is deleted
else
stopLink->prev = 0;
} else {
q->next = stopLink;
if ( stopLink == 0 )
last = q;
else
stopLink->prev = q; // q->prev = q;
}
//now delete the atoms
while ( start != stop ) {
listIterator<T> next = start;
++next;
delete start.currentLink;
start = next;
}
}
link.cpp
//link.cpp
#include "link.h"
#include "list.h"
template <class T>
link<T>::link( T &v )
{
value = v;
prev = next = 0;
}
|
Demo of use of implemented list
//list_demo.cpp
/*
Because of the use of template when defining the List and link classes,
unfortunately, we do need to include the .cpp files here for the
current compilers.
*/
#include <iostream>
#include "list.cpp"
#include "link.cpp"
template <class T>
void print_list( List<T> &aList )
{
List<T>::iterator start, stop;
start = aList.begin(); stop = aList.end();
while ( start != stop ){
cout << *start << ",\t";
++start;
}
cout << endl;
}
void main()
{
typedef double T;
List<T> aList; //a list
T n;
while ( true ) {
cout << "Enter a number, -99 to terminate: ";
cin >> n;
if ( n == -99 )
break;
aList.push_front( n ); //insert into list at front
} //while
cout << "You have entered the list: " << endl;
print_list( aList );
}
|
//list_demo1.cpp
/*
Because of the use of template when defining the List and link classes,
unfortunately, we do need to include the .cpp files here for the
current compilers.
*/
#include <iostream>
#include "list.cpp"
#include "link.cpp"
template <class T>
void print_list( List<T> &aList )
{
List<T>::iterator start, stop;
start = aList.begin(); stop = aList.end();
while ( start != stop ){
cout << *start << ",\t";
++start;
}
cout << endl;
}
void main()
{
typedef double T;
List<T> aList; //a list
T n;
while ( true ) {
cout << "Enter a number, -99 to terminate: ";
cin >> n;
if ( n == -99 )
break;
aList.push_front( n ); //insert into list at front
} //while
cout << "You have entered the list: " << endl;
print_list( aList );
listIterator<double> itr1;
listIterator<double> itr2;
itr2 = aList.begin();
itr1 = aList.end();
++itr2; ++itr2;
aList.erase( itr2, itr1 );
print_list( aList );
return;
}
|
An Examples: an ordered list class
#ifndef ORDEREDLIST_H
#define ORDEREDLIST_H
//orderedList.h
#include "list.h"
template <class T>
class orderedList : public List<T>{
public:
void add ( T & newValue );
};
template <class T>
void orderedList<T>::add ( T &newValue )
//add a new element to an ordered list
{
List<T>::iterator start, stop;
start = begin();
stop = end();
while ( ( start != stop ) && ( *start < newValue ) )
++start;
insert ( start, newValue );
}
#endif
|
An application example: List Insertion Sort
//insertsort.cpp
#include <vector>
#include "list.cpp"
#include "link.cpp"
#include "orderedlist.h"
template <class T>
void print_list( List<T> &aList )
{
List<T>::iterator start, stop;
start = aList.begin(); stop = aList.end();
while ( start != stop ){
cout << *start << ",\t";
++start;
}
cout << endl;
}
void main()
{
typedef double T;
orderedList<T> sorter;
T n;
while ( true ) {
cout << "Enter a number, -99 to terminate: ";
cin >> n;
if ( n == -99 )
break;
sorter.add( n ); //insert into list in order
} //while
cout << "The sorted list is: " << endl;
print_list( sorter );
}
|
Self-organizing Lists
Self-organizing data structures -- try to improve future performance based on current usage
self-organizing list -- need an extra function to determine if the element is in list, if not, returns false; if yes, element is removed from list and inserted once more to the front
#ifndef SELFORGANIZE_H
#define SELFORGANIZE_H
//selforganize.h ( psuedo code only )
#include "list.h"
template <class T>
class selfOrganizingList: public List<T>{
public:
bool include ( T & value );
};
template <class T>
bool selfOrganizingList<T>::include ( T &value )
//see if argument value occurs in list
{
//first find element is list
List<T>::iterator stop = end();
List<T>::iterator where = find ( begin(), stop, value );
//if not found, return false
if ( where == stop )
return false;
//else remove from list and move to front
if ( where != begin() ) {
erase ( where );
push_front( value );
}
return true;
}
#endif
|