Implementing Linked Lists in C++

Dr. Lawlor, CS 202, CS, UAF

In the Gaddis textbook, Chapter 17 explains this way better than I can here.

Here's a hardcoded two-element linked list:

class listnode {
public:
	int x;
	listnode *next;
};

int foo(void) {
	listnode second; cin>>second.x; second.next=NULL;
	listnode first; cin>>first.x; first.next=&second;

	// Walk the newly created list:
	for (listnode *cur=&first;cur!=NULL;cur=(*cur).next) 
	{
		cout<<"Element of list: "<<(*cur).x<<"\n";
		
	}
	return 0;
}

(Try this in NetRun now!)

Here we assemble the list "headfirst", adding elements at the start of the list like push_front does.

class listnode {
public:
	int x;
	listnode *next;
};

int foo(void) {
	// Build the list
	listnode *head=NULL;
	int newx;
	while (cin>>newx) {
		listnode *p=new listnode;
		p->x=newx;
		p->next=head;
		head=p;
		cout<<"Just read "<<newx<<" into pointer "<<p<<"\n";
	}

	// Walks through the list, printing stuff out
	for (listnode *cur=head;cur!=NULL;cur=(*cur).next) 
	{
		cout<<"Element of list: "<<(*cur).x<<"\n";
		
	}
	return 0;
}

(Try this in NetRun now!)

It's actually a little easier to add list elements at the start of the list like above. To add them at the end of the list, you can loop to the end of the list every time, but it's much more efficient to just keep a pointer to the end of the list:

class listnode {
public:
	int x;
	listnode *next;
};

int foo(void) {
	// Build the list
	listnode *head=NULL;
	listnode *last=NULL;
	int newx;
	while (cin>>newx) {
		listnode *p=new listnode;
		p->x=newx; // (*p).x=newx;
		p->next=NULL; //<- we are the end of the list
		if (head==NULL) { // we are the new start of the list
			head=p; last=p;
		} else { // add to the end of the list
			last->next=p;
			last=p;
		}
		cout<<"Just read "<<newx<<" into pointer "<<p<<"\n";
	}

	// Walks through the list, printing stuff out
	for (listnode *cur=head;cur!=NULL;cur=cur->next) 
	{
		cout<<"Element of list: "<<cur->x<<"\n";
		
	}
	return 0;
}

(Try this in NetRun now!)

Here's the full-on "Abstract Data Type" (ADT) implementation, just like std::list with iterator and everything:

class listnode {
public:
	int x;
	listnode *next;
};

class list {
public:
	listnode *head, *tail;
	list() {head=NULL; tail=NULL;}
	void add(int x) {
		listnode *p=new listnode;
		p->x=x;
		p->next=NULL; //<- we are the end of the list
		if (head==NULL) { // we are the new start of the list
			head=p; tail=p;
		} else { // walk to the end of the list
			tail->next=p; // link onto last element
			tail=p; // we are now the last element
		}
	}
	
	class iterator {
	public:
		listnode *cur;
		void operator++(void) { cur=cur->next; }
		bool operator!=(const iterator &it) {return cur!=it.cur;}
		int operator*(void) {return cur->x;}
		iterator(listnode *c) {cur=c;}
	};
	iterator begin(void) {return iterator(head);}
	iterator end(void) {return iterator(NULL);}
};

int foo(void) {
	// Build the list
	list l;
	int newx;
	while (cin>>newx) {
		l.add(newx);
		cout<<"Just read "<<newx<<" into pointer "<<l.tail<<"\n";
	}

	// Walks through the list, printing stuff out
	for (list::iterator it=l.begin();it!=l.end();++it)
	{
		cout<<"Element of list: "<<(*it)<<"\n";
		
	}
	return 0;
}

(Try this in NetRun now!)

I guarantee you'll read some linked list code sometime in your programming career, but now that we've got std::list, I'm not sure if you'll ever have to write any!