Linked Lists/Java: Difference between revisions

From charlesreid1
No edit summary
Line 1: Line 1:
Linked Lists:
Linked lists are a data structure whereby each element of a list is stored in a structure of linked wrapper objects that simply hold a data value and point to neighbor items. The list is an object that contains only one reference to the beginning of the list. Remaining elements must be obtained from the items in the list themselves.
The linked list structure can be implemented as a singly-linked list or a doubly-linked list. A singly linked list means each list node points only to the next node (or a null pointer if the end of the list). A doubly linked list means each list node points at the prior node as well as the next node.
The purpose of using linked lists is that certain operations become much faster (for example, adding elements to the front or back of a list) when using a linked object data structure than they would be using an array-based data structure, which would need to constantly shift or resize elements.
==Why Linked Lists==
Linked lists are a basic data structure, and the idea is a simple one, on the surface. These are excellent for testing understanding, however, because a Linked List takes practice and experience to implement correctly. This can separate the student who says "Let me try this concept out first..." and knows how to practice, from a student who says "Yes yes, I understand, it's very easy, now on to the next topic" and has not actually sat down to implement any of the basics, let alone the more advanced stuff.
==The Gist of Linked Lists==
Questions about Linked Lists require handling a number of different assumptions, questions, and possible interfaces. Which one you implement depends on the problem and specifications. However, "Linked List" should immediately call to mind the methods in a List ADT (abstract data type) and by extension the methods in a LinkedList ADT.
They are mainly the same, but their level of detail depends on the features of the list.
==List ADT==
==List ADT==


Revision as of 04:18, 1 June 2017

List ADT

LinkedList ADT

Link to implementation on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists

The linked list abstract data type provides the following methods:

  • size
  • isEmpty
  • first
  • last
  • addFirst
  • addLast
  • removeFirst

Furthermore, convenience methods can be added, like:

  • add
  • remove
  • remove(i)
  • removeFirst
  • removeLast


Flags



CSFlag.jpg
Data Structures
Part of Computer Science Notes

This is the staging ground for computer science notes as part of the 2017 CS Study Plan.


Data Structures

Classes of data structures: Abstract Data Types

Array-based and Link-based memory management: ArrayLists and Linked Lists

Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures

Advanced data structures: Advanced Data Structures


Flags  · Template:DataStructuresFlag  · e




CSFlag.jpg
Arrays
Part of Computer Science Notes

Series on Data Structures


Arrays Study Guide


Arrays

Python: Arrays/Python  · Arrays/Python/Sizeof  · Arrays/Python/AppendCost  · Arrays/Python/CaesarCipher  · Arrays/Python/CompactArrays  · Arrays/Python/DynamicArray

Java: Arrays/Java  · Arrays/Java/CaesarCipher  · Arrays/Java/FisherYates  · Arrays/Java/PythonList  · Arrays/Java/Repeatedly_Remove

Categories: Category:Python Arrays


Flags  · Template:ArraysFlagBase  · e




CSFlag.jpg
Stacks and Queues
Part of Computer Science Notes

Series on Data Structures


StacksQueues


Stacks and Queues: Python

StacksQueues/Python  · StacksQueues/Python/ArrayStack  · StacksQueues/Python/ArrayQueue  · StacksQueues/Python/ArrayDeque

StacksQueues/Python/LinkedStack


Stacks and Queues: Java

StacksQueues/Java  · StacksQueues/Java/ArrayStack  · StacksQueues/Java/ArrayQueue  · StacksQueues/Java/ArrayQueueFS  · StacksQueues/Java/ArrayDeque

StacksQueues/Java/LinkedStack  · StacksQueues/Java/LinkedQueue  · StacksQueues/Java/LinkedDeque


Applications

Postfix_Expressions#Stacks  · StacksQueues/Subsets  · StacksQueues/Subsets/Java


Flags  · Template:StacksQueuesFlagBase  · e




CSFlag.jpg
Priority Queues and Heaps
Part of Computer Science Notes

Series on Data Structures


Priority Queues

Java: Priority Queues/Java  · Priority Queues/ADT  · Priority Queues/Sorted  · Priority Queues/Unsorted

Performance: Priority Queues/Timing and Performance

Applications: Maximum Oriented Priority Queue  · Priority Queues/Stack


Heaps

Priority Queues/Heap  · Priority Queues/Java  · Priority Queues/Comparators

Heap Sort


Flags  · Template:PriorityQueuesFlagBase  · e




CSFlag.jpg
Linked List
Part of Computer Science Notes

Series on Data Structures


Lists Study Guide


Linked Lists

Java: Linked Lists/Java  · Linked Lists/Java/Single  · Linked Lists/Java/Double  · Linked Lists/Java/Circular

Performance: Linked Lists/Java/Timing  · Linked Lists/Java/Reverse

Python: Linked Lists/Python  · Linked Lists/Python/Single


Flags  · Template:LinkedListFlagBase  · e




CSFlag.jpg
Trees
Part of Computer Science Notes

Series on Data Structures


Trees Study Guide


Trees

Abstract data type: Trees/ADT

Concrete implementations: Trees/LinkedTree  · Trees/ArrayTree  · SimpleTree



Tree Traversal

Preorder traversal: Trees/Preorder

Postorder traversal: Trees/Postorder

In-Order traversal: Binary Trees/Inorder

Breadth-First Search: BFS

Breadth-First Traversal: BFT

Depth-First Search: DFS

Depth-First Traversal: DFT

OOP Principles for Traversal: Tree Traversal/OOP  · Tree Traversal/Traversal Method Template

Tree operations: Trees/Operations Performance  · Trees/Removal



Tree Applications

Expression Trees

Finding Minimum in Log N Time: Tree/LogN Min Search



Binary Trees

Abstract data type: Binary Trees/ADT

Concrete implementations: Binary Trees/LinkedBinTree  · Binary Trees/ArrayBinTree

Binary Trees/Cheat Sheet  · Binary Trees/OOP  · Binary Trees/Implementation Notes



Flags  · Template:TreesFlagBase  · e





CSFlag.jpg
Search Trees
Part of Computer Science Notes

Series on Data Structures


Search Trees

Binary Search Trees  · Balanced Search Trees

Trees/OOP  · Search Trees/OOP  · Tree Traversal/OOP  · Binary Trees/Inorder



Heaps

(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)



Flags  · Template:SearchTreesFlagBase  · e




CSFlag.jpg
Maps and Dictionaries
Part of Computer Science Notes

Series on Data Structures


Maps and Sets Study Guide  · Hash Tables Study Guide


Maps/Dictionaries

Maps  · Maps/ADT  · Maps in Java  · Maps/OOP  · Maps/Operations and Performance

Multimaps  · Guava Maps

Map implementations: Maps/AbstractMap  · Maps/UnsortedArrayMap  · Maps/SortedArrayMap

Dictionaries

Dictionary implementations: Dictionaries/LinkedDict  · Dictionaries/ArrayDict


Hashes

Hash Maps/OOP  · Hash Maps/Operations and Performance

Hash Maps/Dynamic Resizing  · Hash Maps/Collision Handling with Chaining

Hash functions: Hash Functions  · Hash Functions/Cyclic Permutation

Hash map implementations: Hash Maps/AbstractHashMap  · Hash Maps/ChainedHashMap


Skip Lists

Skip Lists  · Java/ConcurrentSkipList  ·

Java implementations: SkipList


Sets

Sets  · Sets/ADT  · Sets in Java  · Sets/OOP  · Multisets


Flags  · Template:MapsFlagBase  · e





GraphFlag.png
Graphs
notes on graph theory, graph implementations, and graph algorithms

Part of Computer Science Notes

Series on Data Structures


Graphs


Graph Theory:

Graphs/Definitions  · Graphs/Matching  · Graphs/Connectivity

First Theorem of Graph Theory


Graph Implementations:

Graphs/Data Structures  · Graphs/ADT

Graphs/Java/Adjacency Map  · Graphs/Java/Adjacency Map Lite

Graphs/Guava


Graph Algorithms:

Algorithms/Graphs


Traversal:

Graphs/Traversal  · Graphs/Euler Tour  · Graphs/Depth First Traversal  · Graphs/Breadth First Traversal

Category:Traversal


Connectivity and Cycles:

Graphs/Finding Cycles  · Graphs/Finding Connected Components  · Graphs/Reachability


Transitive Closure:

Graphs/Transitive Closure  · Graphs/Floyd Warshall Algorithm


Shortest Path:

Graphs/Shortest Path  · Graphs/Edge Relaxation  · Graphs/Dijkstra


Minimum Spanning Tree:

Graphs/Minimum Spanning Tree  · Graphs/Prim Jarnik Algorithm  · Graphs/Kruskal Algorithm

Graphs/Cluster Finding


Directed Acyclic Graphs:

DAGs  · Graphs/Cycles  · Graphs/Topological Sort


Category:Graphs  · Category:Algorithms  · Category:CS  · Category:Data Structures


Flags  · Template:GraphsFlagBase  · e




Retrieved from "https://charlesreid1.com/w/index.php?title=Linked_Lists/Java&oldid=17669"