Information for Program Including Notes and Explanation of LinkedLists

Table of Contents

• [About me]
• [Program Information]
• [Data Structures]
• [Linked Lists]
• [Linked List UML Diagram]
• [Linked List Effeciency]

About Me

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

Program Information

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"

Data Structures

To understand LinkedLists you must first understand data structures and how they are used within lists\

Static Vs. Dynamic Data Structures

• 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

Linked Lists

Consider an object that contains a reference to another object of the same type:

class Node
{

    String name;
    Node pointer;

}

1. This can construct a linked list

2. Delete an entry from a linked list

3. Insert an element into the linked list

Below is the basic information for constructing a linked list

Note: You need to be careful in boundary cases such as operations at the beginning and the end of a list.

LinkedList Code

Linked List UML Diagram

This UML Diagram explains the reference from LinkedList to LinkedListIterator and listIterator

Linked List Effeciency

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