Big Java 4

Chapter 16 – Basic Data Structures

Chapter Goals

peoplelinked on a beach

Implementing Linked Lists - The Node Class

Implementing Linked Lists - The Node Class

Implementing Linked Lists - Adding and Removing the First Element

Implementing Linked Lists - Adding the First Element

Implementing Linked Lists - Removing the First Element

Implementing Linked Lists - Removing the First Element

The Iterator Class

The Iterator Class

Advancing an Iterator

Advancing an Iterator

Removing an Element

Removing an Element

Adding an Element

Adding an Element

Setting an Element to a Different Value

Efficiency of Linked List Operations

Efficiency of Linked List Operations

Efficiency of Linked List Operations

Efficiency of Linked List Operations

Efficiency of Linked List Operations

Efficiency of Linked List Operations

Efficiency of Linked List Operations

Efficiency of Linked List Operations

Efficiency of Linked List Operations

efficiency table

section_1/LinkedList.java

Your browser does not support this feature

section_1/ListIterator.java

Your browser does not support this feature

Self Check 16.1

Trace through the addFirst method when adding an element to an empty list.

Self Check 16.2

Conceptually, an iterator is located between two elements (see Figure 9 in Chapter 15). Does the position instance variable refer to the element to the left or the element to the right?

Self Check 16.3

Why does the add method have two separate cases?

Self Check 16.4

Assume that a last reference is added to the LinkedList class, as described in Section 16.1.8. How does the add method of the ListIterator need to change?

Self Check 16.5

Provide an implementation of an addLast method for the LinkedList class, assuming that there is no last reference.

Self Check 16.6

Expressed in big-Oh notation, what is the efficiency of the addFirst method of the LinkedList class? What is the efficiency of the addLast method of Self Check 5?

Self Check 16.7

How much slower is the binary search algorithm for a linked list compared to the linear search algorithm?

Static Classes

Implementing Array Lists

Implementing Array Lists

Implementing Array Lists - Getting and Setting Elements

Implementing Array Lists - Getting and Setting Elements

Removing or Adding Elements

Removing or Adding Elements

Removing or Adding Elements

Growing the Internal Array

A full trash can

 

 

When an array list is completely full, we must move the contents to a larger array.

 

Growing the Internal Array

Growing the Internal Array

reallocation the internal array

Growing the Internal Array

Efficiency of Array List and Linked List Operations

efficiency of array list and linked list

Self Check 16.8

Why is it much more expensive to get the kth element in a linked list than in an array list?

Self Check 16.9

Why is it much more expensive to insert an element at the beginning of an array list than at the beginning of a linked list?

Self Check 16.10

What is the efficiency of adding an element exactly in the middle of a linked list? An array list?

Self Check 16.11

Suppose we insert an element at the beginning of an array list, and the internal array must be grown to hold the new element. What is the efficiency of the add operation in this situation?

Self Check 16.12

Using big-Oh notation, what is the cost of adding an element to an array list as the second-to-last element?

Implementing Stacks and Queues

Stacks as Linked Lists

Stacks as Linked Lists

section_3_1/LinkedListStack.java

Your browser does not support this feature

Stacks as Arrays

Queues as Linked Lists

Queues as Linked Lists

queue implemented as linked list
queue implemented as linked list

Figure 12 A Queue Implemented as a Linked List

Queues as Circular Arrays

Queues as Circular Arrays

efficiency of stack and queue

Self Check 16.13

Add a method peek to the Stack implementation in Section 16.3.1 that returns the top of the stack without removing it.

Self Check 16.14

When implementing a stack as a sequence of nodes, why isn't it a good idea to push and pop elements at the back end?

Self Check 16.15

When implementing a stack as an array, why isn’t it a good idea to push and pop elements at index 0?

Self Check 16.16

What is wrong with this implementation of the empty method for the circular array queue?
public boolean empty()
{
   return head == 0 && tail == 0;
}

Self Check 16.17

What is wrong with this implementation of the empty method for the circular array queue?
public boolean empty()
{
   return head == tail;
}

Self Check 16.18

Have a look at the growIfNecessary method of the CircularArrayQueue class. Why isn’t the loop simply:
for (int i = 0; i < elements.length; i++)
{
   newElements[i] = elements[i];
}

Implementing a Hash Table

Implementing a Hash Table

hash codes gor some strings

Hash Tables

Hash Tables

Hash Tables

same type of candy in the same bucket

 

 

Elements with the same hash code are placed in the same bucket.

Implementing a Hash Table - Finding an Element

Adding and Removing Elements

Adding and Removing Elements

Iterating over a Hash Table

Iterating over a Hash Table

Hash Table Efficiency

section_4/HashSet.java

Your browser does not support this feature

section_4/HashSetDemo.java

Your browser does not support this feature Program Run:

Self Check 16.19

If a hash function returns 0 for all values, will the hash table work correctly?

Self Check 16.20

If a hash table has size 1, will it work correctly?

Self Check 16.21

Suppose you have two hash tables, each with n elements. To find the elements that are in both tables, you iterate over the first table, and for each element, check whether it is contained in the second table. What is the big-Oh efficiency of this algorithm?

Self Check 16.22

In which order does the iterator visit the elements of the hash table?

Self Check 16.23

What does the hasNext method of the HashSetIterator do when it has reached the end of a bucket?

Self Check 16.24

Why doesn’t the iterator have an add method?