/*#########################################################
HEADER FILE "linked_list.h":
###########################################################*/

/* Joe Pea - Linked List */

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <cstdlib>  // Provides size_t
#include "node.h"  // Provides node class

namespace CISP430_A5
{
    template <class Item>
    class linked_list
	/*TODO: * Optimize so that we don't have to iterate through each address to reach a desired position.
			  Make a "position" field for each Node object or something?
			  Or create a "last_position" variable in this class so we can iterate forward
			  or backward from the last position instead of from the beginning each time?
			* Add post and pre conditions for all the new functions above.
	*/
	/**
			The /*REMOVED*//*, /*STAYS THE SAME*//*, and /*ADDED*//* comments show the 
			differences in converting from the sequence class to the linked_list class.
	*/
    {
		public:
		/* TYPEDEFS and MEMBER CONSTANTS: */
			typedef Item value_type;
			typedef size_t size_type;
			
		
		
		/* CONSTRUCTORS and DESTRUCTOR: */
			linked_list( );
			linked_list(const linked_list& source);
			~linked_list( );
			
		
		
		/* MODIFICATION MEMBER FUNCTIONS */
			/*ADDED:*/
				value_type get(int position); // get item at position x
				void set(int position, const value_type& entry); // set item at position x, if past boundaries, just modify at beginning or at end.
				void add(const value_type& entry); // add to the end of list
				void insert(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
				void attach(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
				void remove(int position);
		
			/*REMOVED:*/
				/*void remove_current( );*/
				/*void start( );*/
				/*void advance( );*/
				/*void insert(const value_type& entry);*/
				/*void attach(const value_type& entry);*/
		
			/*STAYS THE SAME:*/
				void operator=(const linked_list& source);
			
		
		
		/* CONSTANT MEMBER FUNCTIONS */
			/*STAYS THE SAME:*/
				value_type current( ) const;
				size_type size( ) const { return many_nodes; }
				bool is_item( ) const { return (cursor != NULL); }

		
		
		private:
		/*PRIVATE HELPER FUNCTIONS*/
			/*ADDED:*/
				void remove_current( );
				void start( );
				void advance( );
				void insert_here(const value_type& entry); // same as insert() from sequence. insert at current position.
				void attach_here(const value_type& entry); // same as attach() from sequence. attach at current position.
		
		
		
		/*PRIVATE VARIABLES*/	
			/*STAYS THE SAME:*/
				node<Item> *cursor;
				node<Item> *precursor;
				node<Item> *head_ptr;
				node<Item> *tail_ptr;
				size_type many_nodes;
    };
}





/* Sample usage:
int main(void) {

	linked_list items = new linked_list;
	items.attach(10);
	items.insert(30);
	items.attach(20);
	items.insert(40);

	// for each item in the list:
	for (int i=0; i<items.size(); ++i) {
		cout << items.get(i) << endl;
	}
	
	items.set(2, 50);
	// item at position 2 is now 50.
}
*/




// The implementation of a template class must be included in its header file:
#include "linked_list.template"
#endif

/*#########################################################
TEMPLATE FILE "linked_list.template":
###########################################################*/


/* Joe Pea - CISP430 Assignment 5 */

namespace CISP430_A5 {
/*I've marked lines/blocks as REMOVED or ADDED in order to tell what I changed
	from the sequence class to create my ideal linked_list class*/
/*TODO: Add previous field to Node class and remove usage of precursor.*/
			
	/* CONSTRUCTORS and DESTRUCTOR */
	
	template <class Item>
	linked_list<Item>::linked_list() {
		head_ptr = NULL;
		tail_ptr = NULL;
		cursor = NULL;
		precursor = NULL; // no need for this if Node objects have a "previous" link field.
		many_nodes = 0;
	}
	
	template <class Item>
	linked_list<Item>::linked_list( const linked_list& source ) { // copier
		
		int src_size = source.size(); // to replicate cursor position
		int many_til_end = 0; // to replicate cursor position
		int many_til_mid = 0; // to replicate cursor position
		node<Item> *src_cursor = source.cursor; // to replicate cursor position
		
		list_copy(source.head_ptr, head_ptr, tail_ptr);
		
		/*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
			many_nodes = source.many_nodes;
		
		/*replicate the cursor position*/
			if (src_cursor != NULL) {
				while (src_cursor != NULL) {
					++many_til_end;
					src_cursor = src_cursor->link();
				}
				many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
				start(); // put this.cursor at beginning. // DEPENDS ON VALUE OF many_nodes ABOVE
				for (int i=0; i<many_til_mid; ++i) {
					advance(); // DEPENDS ON VALUE OF many_nodes ABOVE
				}
				/* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
			}
			else {
				cursor = NULL;
				precursor = NULL;
			}
	}
	
	template <class Item>
	linked_list<Item>::~linked_list() { // Destructor
		list_clear(head_ptr);
		head_ptr = tail_ptr = cursor = precursor = NULL;
		many_nodes = 0;
	}
			
	/* MODIFICATION MEMBER FUNCTIONS */
	
	template <class Item>
	void linked_list<Item>::start() {
		if (many_nodes > 0) { // if at least one item exists
			cursor = head_ptr;
			precursor = NULL;
		}
	}
	
	template <class Item>
	void linked_list<Item>::advance() {
		if (is_item()) {
			precursor = cursor;
			cursor = cursor->link();
			if ( cursor == NULL ) {
				precursor = NULL;
			}
		}
	}
	
	/*
	ADDED [
	*/
		template <class Item>
		typename linked_list<Item>::value_type linked_list<Item>::get(int position) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then return item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					return current();
				}
			}
		}
		
		template <class Item>
		void linked_list<Item>::set(int position, const value_type& entry) {
			if (is_item()) { // only set at a valid position.
			
				insert(position, entry); // insert new item to list
				
				advance();
				remove_current(); // remove old item from list.
			}
		}
		
		template <class Item>
		void linked_list<Item>::add(const value_type& entry) {
			cursor = precursor = NULL; // remove cursor
			attach_here(entry); // <<-- attaches at end when no cursor.
		}
		
		template <class Item>
		void linked_list<Item>::remove(int position) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					remove_current();
				}
			}
		}
		
		template <class Item>
		void linked_list<Item>::insert(int position, const value_type& entry) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					insert_here(entry);
				}
			}
		}
	/*
	]
	*/
	
	template <class Item>
	void linked_list<Item>::insert_here(const value_type &entry) {
	/*REMOVED*/
		// void linked_list<Item>::insert(const value_type &entry) {
		
		/*if the list is empty*/
		if (!is_item() && !many_nodes) {
			cursor = new node<Item>(entry);
			head_ptr = cursor;
			tail_ptr = cursor;
		}
		
		/*if the list is not empty and cursor points to the first item*/
		else if (is_item() && cursor == head_ptr) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr );
			head_ptr = cursor;
		}
		
		/*if the list is not empty and there is no current item*/
		else if (!is_item() && many_nodes) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr );
			head_ptr = cursor;
		}
		
		/*if the list is not empty and the cursor points somewhere in 
			the middle(including last item)*/
		else if (is_item() && cursor != head_ptr) {
			cursor = new node<Item>( entry );
			cursor->set_link( precursor->link() );
			precursor->set_link( cursor );
		}
		
		++many_nodes; //increase the node count
	}
	
	/*ADDED*/
		template <class Item>
		void linked_list<Item>::attach(int position, const value_type& entry) {
			for (int i=0; i<=position; ++i) { // advance the cursor to the position then attach item
				if (i==0)
					start();
				else
					advance();
				
				if (i==position) {
					attach_here(entry);
				}
			}
		}
	
	template <class Item>
	void linked_list<Item>::attach_here(const value_type& entry) {
	/*REMOVED*/
		// void linked_list<Item>::attach(const value_type& entry) {
		
		/*if the list is empty*/
		if (!is_item() && !many_nodes) {
			cursor = new node<Item>(entry);
			head_ptr = cursor;
			tail_ptr = cursor;
			precursor = NULL;
		}
		
		/*if the list is not empty and cursor points to the first item and there's only one item*/
		else if (is_item() && many_nodes == 1) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr->link() );
			head_ptr->set_link( cursor );
			precursor = head_ptr;
			tail_ptr = cursor;
		}
		
		/*if the list is not empty and cursor points to the first item and there's more than one item*/
		else if (is_item() && many_nodes > 1 && cursor == head_ptr ) {
			cursor = new node<Item>( entry );
			cursor->set_link( head_ptr->link() );
			head_ptr->set_link( cursor );
			precursor = head_ptr;
		}
		
		/*if the list is not empty and there is no current item*/
		else if (!is_item() && many_nodes) {
			cursor = new node<Item>( entry );
			tail_ptr->set_link( cursor );
			precursor = tail_ptr;
			tail_ptr = cursor;
		}
		
		/*if the list is not empty and the cursor points somewhere in 
			the middle(including last item)*/
		else if (is_item() && cursor != head_ptr) {
			if (cursor != tail_ptr) { // if cursor is not at last item
				cursor = new node<Item>( entry );
			}
			else if (cursor == tail_ptr) { // if cursor is at last item
				cursor = new node<Item>( entry );
				tail_ptr = cursor;
			}
			cursor->set_link( (precursor->link())->link() );
			(precursor->link())->set_link( cursor );
			precursor = precursor->link();
		}
		
		++many_nodes; // increase the node count
	}
	
	template <class Item>
	void linked_list<Item>::remove_current() {
		if ( is_item() ) {
			
			/*If the cursor points to an item in the middle of the list, not tail, not head:*/
			if (cursor != head_ptr && cursor != tail_ptr) {
				precursor->set_link( cursor->link() );
				delete cursor;
				cursor = precursor->link();
			}
		
			/*If the cursor points to the first item in the list and that is the only item:*/
			else if (many_nodes == 1) {
				delete cursor;
				cursor = head_ptr = tail_ptr = precursor = NULL;
			}
			
			/*If the cursor points to the first item in the list and there is more than one item:*/
			else if ( cursor == head_ptr && many_nodes > 1) {
				cursor = cursor->link();
				delete head_ptr;
				head_ptr = cursor;
			}
			
			/*If the cursor points to the last item in the list (and there is more than one item)*/
			else if ( cursor == tail_ptr && many_nodes > 1) {
				delete cursor;
				tail_ptr = precursor;
				/* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
				tail_ptr->set_link(NULL);
				/* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
				precursor = cursor = NULL;
			}
			
			--many_nodes;
		}
	}
	
	template <class Item>
	void linked_list<Item>::operator =(const linked_list& source) {
		if (this != &source) {
			list_clear(head_ptr);
			head_ptr = tail_ptr = cursor = precursor = NULL;
			many_nodes = 0;
		
			int src_size = source.size(); // to replicate cursor position
			int many_til_end = 0; // to replicate cursor position
			int many_til_mid = 0; // to replicate cursor position
			node<Item> *src_cursor = source.cursor; // to replicate cursor position
			
			list_copy(source.head_ptr, head_ptr, tail_ptr);
			
			/*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
				many_nodes = source.many_nodes;
			
			/*replicate the cursor position*/
				if (src_cursor != NULL) {
					while (src_cursor != NULL) {
						++many_til_end;
						src_cursor = src_cursor->link();
					}
					many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
					start(); // put this.cursor at beginning.
					for (int i=0; i<many_til_mid; ++i) {
						advance();
					}
					/* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
				}
				else {
					cursor = NULL;
					precursor = NULL;
				}
		}
	}
			
	/* CONSTANT MEMBER FUNCTIONS */
	
	template <class Item>
	typename linked_list<Item>::value_type linked_list<Item>::current() const {
		if ( is_item() ) {
			return cursor->data();
		}
	}

}

http://keepskatinbro.com

This is a linked list that can be used like an array where instead of using [] after the reference you just used .get() (and some other methods) but now you don't have to worry about sizing.

For example, with an array you would do:

    cout << foobar[3] << endl;

But with my linked list you do:

    cout << foobar.get(3) << endl;

With an array:

    foobar[2] = 5;

With my Linked List:

    foobar.set(2, 5);

The syntax differences are minor, but the usage is just as easy as an array and you don't have to worry about how big your "array" will be.

Keep in mind that you also need to include a single-link node class in your code for use with this linked_list class. I'll post one sometime hehe.

My linked_list class (both the header file and the template file)

list

C++