MyLinkedList Program
Description
This program builds a generic singly linked list data structure.
It defines a class Node to store a reference to an element and
a reference, called next, to another node.
The objects of Node class are used to build a singly linked list data structure called MyLinkedList.
MyLinkedlist class includes commonly defined methods, such as
addFirst( newObj ), removeFirst(), addLast ( newObj ), search( keyObj ), traverse(), and etc.
The program also defines EmptyListException class to handle the empty list exception.
The client program builds a MyLinkedList object and tests the methods defined in the class.
The objects of Node class are used to build a singly linked list data structure called MyLinkedList.
MyLinkedlist class includes commonly defined methods, such as
addFirst( newObj ), removeFirst(), addLast ( newObj ), search( keyObj ), traverse(), and etc.
The program also defines EmptyListException class to handle the empty list exception.
The client program builds a MyLinkedList object and tests the methods defined in the class.
Associated Concepts:
Singly Linked List
Algorithm:
Node class
MyLinkedList class
Client program
EmptyListException class
Two private data members: a generic object and a reference to another node.
Constructors.
Setters and getters.
Constructors.
Setters and getters.
MyLinkedList class
Three private data members: head, tail, and size.
Constructor.
getSize(), isEmpty(), addFirst(), removeFirst(), addLast(), and traverse() methods.
getSize() method
isEmpty() method
void addFirst(E object) method
E removeFirst() method
void addLast(E object) method
String traverse() method
Constructor.
getSize(), isEmpty(), addFirst(), removeFirst(), addLast(), and traverse() methods.
getSize() method
Return the number of nodes in the linked list.
isEmpty() method
Return true if the head reference is null; false otherwise.
void addFirst(E object) method
1. Create a new node for the passed parameter object.
2. Have the new node point to the current head of the linked list.
3. Update the head reference to point to the new node.
4. Increase the size.
2. Have the new node point to the current head of the linked list.
3. Update the head reference to point to the new node.
4. Increase the size.
E removeFirst() method
1. Check for the empty list.
2. Assign the head reference to a temporary head.
3. Retrieve the element at the head (result).
4. Update the head to point to the next node in the list.
5. Null out the next reference of the removed node.
(Allow garbage collector to reclaim the former first node)
6. Decrease the size.
7. Return the result.
2. Assign the head reference to a temporary head.
3. Retrieve the element at the head (result).
4. Update the head to point to the next node in the list.
5. Null out the next reference of the removed node.
(Allow garbage collector to reclaim the former first node)
6. Decrease the size.
7. Return the result.
void addLast(E object) method
(Tail pointer should be set properly.)
1. Create a new node for the passed parameter object.
2. Have the new node point to null.
3. Have the current last node point to the new node.
4. Update the tail to point to the new node.
5. Increase the size.
1. Create a new node for the passed parameter object.
2. Have the new node point to null.
3. Have the current last node point to the new node.
4. Update the tail to point to the new node.
5. Increase the size.
String traverse() method
1. Check for the empty list.
2. Assign a temporary reference (temp) to the head reference.
3. Declare a string to store the result.
4. In a loop, visit each node, retrieve the object in the node, and add the object to the result.
5. Return the result after the loop is ended.
2. Assign a temporary reference (temp) to the head reference.
3. Declare a string to store the result.
4. In a loop, visit each node, retrieve the object in the node, and add the object to the result.
5. Return the result after the loop is ended.
Client program
Create a MyLinkedList object.
Call the methods defined in the MyLinkedList class to test them.
Call the methods defined in the MyLinkedList class to test them.
EmptyListException class
Extend the RuntimeException class.
Invoke the superclass' constructor in the constructor.
Invoke the superclass' constructor in the constructor.
Source Code
Node class
MyLinkedList class
Client program
EmptyListException class
Sample Run
