Information for Program Including Notes and Explanation of LinkedLists
- About me
- Program Information
- Data Structures
- Linked Lists
- Linked List UML Diagram
- Linked List Effeciency
At the time of writing this program I am a Freshman at Arizona State University studing Computer Systems Engineering in my second semester. Due to the recent events of COVID-19 and complications with living at home and working on all classes from home I have extra time to work on these programs and develop a more understandable version of programs that I have developed.
Hopefully all explanations here work... if not feel free to contact me at:
ashinhust.brass@gmail.com
This program displays a menu of choices which allows the user to develop a list
Once this list is developed the user can perform operations on this list which are provided
Choices
"A Add String"
"C Count Strings"
"D Duplicate Each"
"H How Many Appear Before"
"I Index Of Last"
"L List Strings"
"Q Quit"
"R Remove from Even Indices"
"S Remove String at some Index"
"? Display Help"
To understand LinkedLists you must first understand data structures and how they are used within lists\
- A static data structure has a fixed size (Arrays)
int[] numbers = new int[size]
- Dynamic data structures grow and shrink as required by the information it contains (LinkedLists)
An object reference is a var that stores the address of an object
A reference is also called a pointer
Object references can be used to create links between objects
Consider an object that contains a reference to another object of the same type:
class Node
{
String name;
Node pointer;
}
Note: You need to be careful in boundary cases such as operations at the beginning and the end of a list.
This UML Diagram explains the reference from LinkedList to LinkedListIterator and listIterator
Let's compare the effeciency of using a linkedList compared to an ArrayList\
-
In ArrayList, we can access any element by specifying its index in constant time. – O(1)
-
In LinkedList, we need to go through n/2 elements on average to get to an element. – O(n)
-
In ArrayList, adding or removing an element can take O(n) (=O(n/2) on average) because of shifting all elements.
-
In LinkedList, adding or removing an element can be done in constant time, assuming that the iterator is already in the right position – O(1)
NOTE: This all depends on the algorithm that we are writing and what it calls for