Java

TOPIC 19 – JAVA COLLECTIONS I - LISTS

 

 

LESSON NOTE

 

 

INTRO

 

A data structure is literally a digital structure that organizes data in memory so that it can be used efficiently.  Efficiency is determined by both memory usage and time required to manipulate the data structure.

 

Different data structures have different pros and cons.  Some take up a lot of memory but can be faster to work with.  Others take up little memory but require move CPU cycles to manipulate.  And others provide different options such as the sorting of the data or keeping the data in a specific order.

 

OUR FIRST DATA STRUCTURE: ARRAY

 

You've already worked with a data structure – an array.  Arrays are the best known data structures because they are fairly simple to understand but also because they exist as a basic part of most programming languages. 

 

Java is an example of such a language with arrays being supported at the most basic level.  All other data structures require libraries to use them – of course, that is very easy to do in Java (a simple import statement will do) so there is no reason to use only arrays.

 

JAVA COLLECTIONS

 

Java actually has many implementations of different data structures.  They all extend the Collection class and are often referred to as Java Collections. 

 

Before we get into that, let's take a step back and further discuss the idea of a data structure.

 

ABSTRACT DATA TYPES (ADTs)

 

An abstract data type (ADT) is a mathematical model of how a data structure should work.  It is simply the general rules about a data structure.  It does not consider details about a specific implementation.  This way, the functionality of a certain data structure in Java should be similar to that structure in any other language.

 

Being able to talk about abstract data types allows computer scientists to evaluate their efficiency outside of any programming language.

 

COMMON ABSTRACT DATA TYPES

 

Here are different ADTs and some of their general characteristics:

 

LIST

  • Stores different elements in a specific order.
  • Can add, remove and access (see) elements anywhere in the list by using an index number
  • Note: An array is similar to a list except the arrays we've used cannot be resized. 

 

SET

  • Stores different elements in no specific order.
  • Does not allow for duplicates.

 

MAP

  • Stores pairs of data together.  One piece is called the key and the other is called the value.
  • Keys cannot be duplicated.  The values can be.
  • We can give the map a key and it will return the associated value.
  • Note: Also called associative array.

 

QUEUE

  • Stores elements based on the order they "arrive".
  • We can add to the structure at one end only.
  • We can get (remove) elements from one end only.
  • Varieties: Queue, Stack, Priority Queue

 

The different ADTs described above are only models.  The actual implementations of such models have their own details that need to be learned as well. 

 

There are also many other ADTs.  Some other well known structures are graphs and trees.

 

DIFFERENT IMPLEMENTATIONS

 

It is also important to note that there are very different implementations possible for each ADT.  While all implementations provide the same working approach, each implementation has its own pros and cons.

 

IMPLEMENTATIONS IN JAVA

 

Here are some commonly used data structure classes in Java

 

List Implementations:

  • ArrayList
  • LinkedList

 

Set Implementations:

  • HashSet
  • TreeSet

 

Map Implementations:

  • HashMap
  • TreeMap

 

Queue Implementations & Varieties:

  • Queue (I think)
  • PriorityQueue
  • Stack
  • Deque