ht3886 / dlinkedlist_java Goto Github PK
View Code? Open in Web Editor NEWThis program exhibits a data structure that looks like a set of linked list but mimics some behavior of a balanced binary tree.
This program exhibits a data structure that looks like a set of linked list but mimics some behavior of a balanced binary tree.
Overview ------------ This program exhibits a data structure that looks like a set of linked list but mimics some behavior of a balanced binary tree. The program accepts data values from the user and allows the user to search the list to see if a value is in this list. The main purpose of the data structure is to store the data. The summary of allowed operations and their restrictions are in the csci 3901 course assignment #2 information in the course's Brightspace space. This program does not use any data structures from the Java Collection Framework. The main idea is to store data randomly in a hierarchical manner so that search can be performed in a low time complexity. The data structure implements some of the functionalities of both a doubly linked list and binary balanced tree where the former is used while storing data and the latter allows us to search data quickly. - elements are present in a sorted manner in each level. -data will be added firstly in the lowest list, keeping the sorted order. Once inserted, we randomly choose weather or not the new item should go into the list above. -we keep adding data to new higher levels based on the random value. -while searching for a value, we begin search in the highest level. If not found, we would then follow the link to next lower level. -we will be using a constructor "coin" to randomly decide if key will be added to the next level. The sequence of our class file will be: - Flip coin to determine number of levels. - Add key to the data structure based on levels decided by coin flip. - Search for a key in data structure. Files and external data ------------------------------ There are total five files: - ListHierarchy.java -- class that stores the data structure and allows add and find operations to be performed - SkipUI.java -- main for the program that manages user input until they provide the command "quit" - RandomCoin.java -- class that implements the interface coin and generates random value among 0 or 1 - ArrayCoin.java -- class that implements the interface coin and lets us specify coin flips which can help us in debugging. - Coin.java -- An Interface class that declares flip method Constructor and Methods with their significance ----------------------------------------- add -- A method of return type boolean, it is used to add a key to the data structure. Returns true if the key can be found in the list (return true if key is already in the list too) find -- A method of return type booelan, it is used to search the data structure for the key value. ListHierachy -- constructor that accepts objects of type to deliver random values. Returns true if the object is ready to be used at the end of method call. Data structures and design elements ----------------------------------------------------------------- The program stores data every time in a node which is defined in java bean class named "myNode". The class "myList" is used to perform add and find operations in the list by creating a object of class "myNode". The data structure is designed in a way that the lowest row acts like a sorted doubly linked list and has branches that are created hierarchically in a random manner. The new key is always added in a sorted manner at each level. The new key is always added first in the lowest row and depending upon positive coin flips, the key is added in higher row levels. If the coin flip has value 0, it means we do not put the new value into the upper list. If coin flip value is 1, we do put it into upper list. When we add a value to upper list, we fetch another random value to determine if we add it into next higher list. This random selection process continues until we are in the topmost list or we have choice to no longer promote the value in a higher list.If in the topmost list, we still get coin flip value 1, we do add a new level to the hierarchy and then stop. Given a value to search, we begin searching in the topmost level. If found we return true, else we move downwards and continue searching in lower levels. Finally, we search in the lowest row which has all the data and if still not found we return false. Assumptions ----------------- - No strings to store will be more than 15 characters. Limitations -------------- - Only user input of type strings will be processed by the data structures - The find operation is performed only if exact match is found (case sensitive)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.