This project is about implementing a set data structure with the use of a node class. It utilizes methods within the linked set that allows for manipulation and retrieval of the data inside.
Section 1: Project Specification The data type I chose for this project was a linked set. A linked list is an abstract data type (ADT), which is a specification of a data set and the operations on that set, However, the way the data is stored or how to implement the operations is not indicated by the specification. The specification is independent of any programming language. The linked set implements an array, which stores nodes. These nodes all reference each other and create a “link.” It is a linear data structure since an array is being used. I chose an array since we are storing string objects in a way that can avoid moving data when adding or removing data by utilizing nodes and the “chain” they make. And because of this, an array allows for removal and addition of objects via retrieving their data portions in a node that references it, which is similar to indexes. However, a linked set does not allow for duplicates. Therefore, methods that would typically be in an array bag, such as getFrequencyOf, are not included since there is no need for such methods. Moreover, this linked set is more dynamic than an array bag would be. Instead of having a set amount in terms of the entries it can store, a linked set simply adds a node to the end to form a chain that does not require a set size. This saves the trouble of doubling an array, and removes and recycles nodes that are not needed. In terms of functionality, the linked set can add entries to the chain either at the beginning or end of the chain with ease, which is similar for the remove methods. To construct the linked set, I had to specify its data and the methods the set will implement. I had to define private variables, such as “numberOfEntries” that holds the number of entries in the set, and “firstNode,” which references the firstNode in the chain. In addition, I had to define a private inner class for Node. In this class, it had a private generic variable “data” that held the entry in each node, and a private Node variable “next” which referenced the next node on the chain. Inside the class were two constructors, a default and parameterized constructor. The default constructor only created a Node that had “data” and no “next.” The parameterized constructor creates a node that has “data” and a “next” to reference. By using private helper methods and public interfaces, the linked set is able to create the so-called “chain” of nodes that can store linear data utilizing an array.