macOS Linked List Question in C++

[unintelligence]

I am writing a basic Linked List class for a project for my Comp. Sci. class.

How should I go about overloading the [n] operator (n being an integer representing position) so that I can access the nth item in my list? I'm basically trying to emulate how vectors allow coders to access items in the list.

Here's the code from my linked list header:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

const int MAX_VALUE=100;	//used to define the maximum length of the linked list

using namespace std;

template <class ItemType> class LinkedList{
	private:
	struct node{
		ItemType item;
		node* next;
	};
	node* start;
	int length;
	ItemType items[MAX_VALUE];
	
	public:
	LinkedList();
	void printList();
	void insert(ItemType i);
	void remove(ItemType i);
	int getListLength();
};

template <class ItemType> LinkedList<ItemType>::LinkedList()
{
	start=NULL;
	//next=NULL;
	length=0;
}

template <class ItemType> int LinkedList<ItemType>::getListLength()
{
	return length;
}

template <class ItemType> void LinkedList<ItemType>::insert(ItemType i)
{
	node* newone=new node;
	newone->item=i;
	newone->next=start;
	start=newone;
	length++;
}

template <class ItemType> void LinkedList<ItemType>::remove(ItemType i)
{
	node* current=start;
	node* trailer=NULL;
	if(start==NULL)
	{
		return;
	}
	while(current!=NULL && current->item!=i)
	{
		trailer=current;
		current=current->next;
	}
	if(current==NULL)
	{
		return;
	}
	if(current==start)
	{
		start=start->next;
	}
	else
	{
		trailer->next=current->next;
	}
	delete current;
	length--;
}

template <class ItemType> void LinkedList<ItemType>::printList()
{
	node* current=start;
	if(current==NULL)
	{
		cout << "List is empty." << endl;
		return;
	}	
	while(current!=NULL)
	{
		cout << current->item << endl;
		current = current->next;
	}
}

#endif

I started trying it by myself without any help, but I don't know how to write the definition or implementation:

template <class ItemType> friend ItemType LinkedList<ItemType>::operator[](int posn, ItemType i)
{
	node* current=start;
	if(posn==0)
		return current->item;
	while(current!= NULL)
	{
		//process current node
		current = current->next;
	}
}

 

[AlmostThere]

Start by deciding whether you want a linked (sequential) or random access list (array-like). That you have both a fixed size array of ItemType and an inner node class suggests you are unclear about what you want. Make sure you are clear about what you want from this class and why you have chosen a linked list, before ploughing on.

Unless it is mandated by your class, I suggest you use the standard C++ list and vector for a while before moving on to designing your own classes for this.

A good place to start would be implementing your class around one of these standard classes and then adding the extra functionality you want (it's probably worth noting that the C++ standard library list doesn't offer random access).

Although it is Java, have a quick read of this article: http://www.onjava.com/pub/a/onjava/2001/05/30/optimization.html which covers linked versus array lists. It also has some code for the function you want on page 2. It is going to be pretty similar to your remove() function.

 

[AlmostThere]

Quick example, with plenty of scope for improvement, showing the syntax for operator[].

Obviously if the point of the exercise is to actually implement the list class, you have to do that yourself, I have a plate of broken glass I would rather eat.

#include <list>
#include <iostream>
#include <stdexcept>

using namespace std;

template<typename T>
class ArrayList
{

    typedef typename list<T>::size_type size_type;
    typedef typename list<T>::iterator  iterator;

public:
    // Leave this public for demo as am not going to add method interface
    list<T> innerList;
    
    ArrayList() 
    {
        innerList = list<T>();
    }
    
    T& operator[] (size_type index) 
    {
        if (index >= innerList.size()) 
            throw range_error("ArrayList index out of bounds");
        
        size_type count = 0;
        iterator iter = innerList.begin(); 
        while (count != index) 
        {
            count++; iter++;
        }
        return *iter;
    }
};


int main()
{

    ArrayList<int> theList;
    for(int i = 100; i<200; ++i)
    {
        theList.innerList.push_back(i);
    }
    
    cout << theList[50] << endl;
    
}

 

[unintelligence]

AlmostThere,

Thank you for your insight, it's very helpful.

May I ask why I have to decide between using nodes or an array-based list?

To clarify, my project requires that I develop my own linked-list class, without using any of the standard libraries.

 

[rev316]

Usually when you implement doubly-linked lists; a node model is the one you should follow. It'll dynamically resize memory to act like a primitive array. From what resources I've collected, it's a preferred way to go with single-linked lists as well.

 

[lazydog]

Yes, I'd go along with nodes too. If you also overload new and delete you can maintain a linked list of 'free' nodes. new() will then allocate from the free list and delete will return the node back into the free list. If your free list should ever run empty simply allocate more nodes and link them into the free list. Effectively you are creating your own node memory manager.

b e n