Linked List

Today we will have the morning part of class time for you to work on your program, as it seems like most of you will need more time for it.

After lunch, we will begin our lecture on a new topic, linked lists. Today's lecture is going to be mostly conceptual -- I'll be explaining how a linked list works conceptually. This will also be an example of how a whole new data structure can be implemented with the help of classes and objects.

Before talking about linked lists, however, we first need to discuss how pointers work with objects. So far we have only used classes we defined as concrete variables, not pointers and dynamically allocated objects. Given that you understand pointers and classes individually, however, this should be easy to pick up.

After going through the concepts of a linked list, we will go over this sample linked list implementation code below.

class ListNode {
  private:
	int value;
	ListNode* next;
  public:
	ListNode() {
		value = 0;
		next = NULL;
	};
	ListNode(int val, ListNode* ne) {
		value = val;
		next = ne;
	};
	friend class LinkedList;
};

class LinkedList {
  private:
	ListNode* head;
  public:
	LinkedList() {
		head = NULL;
	};
	~LinkedList() {
		ListNode *ptr, *temp;
		ptr = head;
		// go thru the list and delete all nodes
		while (ptr != NULL) {
			temp = ptr->next;
			delete(ptr);
			ptr = temp;
		}
	};
	void insert(int val) {
		ListNode *ptr, *prev;
		ptr = head;
		// sorted list. from smallest to largest

		// first the case if list is empty
		if (ptr == NULL) {
			head = new ListNode(val, NULL);
			return;
		}

		// if list is not empty. insert it to the right place
		while (ptr != NULL && ptr->value <= val) {
			prev = ptr;
			ptr = ptr->next;
		}
		if (ptr == head) {
			// if ptr is still at head, that means supposed to insert at head
			head = new ListNode(val, head);
		} else {
			// inserting in the middle or at the end
			prev->next = new ListNode(val, ptr);
		}
	};
	void remove(int val) {
		ListNode *ptr, *prev;
		ptr = head;
		// this function removes the first node found of this value

		while (ptr->value != val) {
			prev = ptr;
			ptr = ptr->next;
		}

		if (ptr != NULL) {
			// if ptr went to NULL, it went thru the list and didnt find value
			// in that case, ignore. only do the remove when theres something to.
			if (ptr == head) {
				// if removing head node
				head = head->next;
				delete(ptr);
			} else {
				// if removing in the middle or end
				prev->next = ptr->next;
				delete(ptr);
			}
		}
	};
	void printList() {
		ListNode *ptr;
		ptr = head;
		while (ptr != NULL) {
			cout<<ptr->value<<" ";
			ptr = ptr->next;
		}
		cout<<endl;
	}
};

The rest of the time of the class will either be for finishing up your previous program, or a new program; depending on the progress of the class with the previous program.

For this program you will have to implement a linked list. What your program has to do is the following: You take in a list of positive integers from user input (with no limit on how many you can enter). You need to keep track of this order, so you will most likely have to insert each number to your linked list each time the user types in a number. When the user types in 0 (zero), you stop prompting. When asked to insert numbers, if a number is already found in the list, do not add it again and say number is duplicated. And then you ask the user numbers that he/she wishes to remove. If the requested number is not in the list, say the number is not found. Again, when the user types in 0, you stop prompting.

At the end of the program, first print out the list you have. And then you reverse the list, and call printList() again to print it out.

Sample flow of the program:

% a.out
Enter a number to insert: 6
Enter a number to insert: 8
Enter a number to insert: 30
Enter a number to insert: 1
Enter a number to insert: 8
8 is already in the list. Try something else.
Enter a number to insert: 17
Enter a number to insert: 0

Enter a number to remove: 30
Enter a number to remove: 9
9 is not in the list. Try something else.
Enter a number to remove: 0

Your list:
6 8 1 17
Reversed list:
17 1 8 6

You are given the following classes to work with. Read the code comments for details.

class ListNode {
  private:
	int value;
	ListNode* next;
  public:
	ListNode() {
		value = 0;
		next = NULL;
	};
	ListNode(int val, ListNode* ne) {
		value = val;
		next = ne;
	};
	friend class LinkedList;
};

class LinkedList {
  private:
	ListNode* head;
  public:
	LinkedList();
	~LinkedList();
	void insert(int val);	// inserts, not sorted. always inserts at the end
	bool remove(int val);	// returns true if successfully removed
				// if number not found, return false
	// printList() MUST NOT BE CHANGED.
	void printList() {
		ListNode *ptr;
		ptr = head;
		while (ptr != NULL) {
			cout<<ptr->value<<" ";
			ptr = ptr->next;
		}
		cout<<endl;
	};
	void reverseList();	// reverse the list. you must actually reverse the list
				// in memory, and not just print them out in reverse order.
};