Questions

• Reading?
• Homework?
• Quiz?

Concept - Linked List

A data structure used for collecting a sequence of objects that allows efficient addition and removal of elements in the middle of the sequence

• Consists of nodes, each of which has a reference to the next node.
• Use when you rarely need elements in random order but do care about the efficiency of adding and removing nodes
• A node consists of data and a link pointing to the next node.
• A doubly-linked linked list also has a link to the previous node.

Concept - Linked Liist

• Insertion
  
• Removal
  

Concept - LinkedkList class of the Java Collections Framework

• In the java.util package
• It is a doubly-linked linked list
  • has a link to both the next and the previous node
• You specify the type of item in angle brackets
• Called a generic class
• To declare an empty LinkedList that can hold a specific type of objects:

  LinkedList<Student> myClass = new LinkedList<>()
  LinkedList<String> names = new LinkedList<>()

• Implements the List interface as well as Collection interface
• Has additional methods

Activity - LinkedkList class of the Java Collections Framework

Record your participation in Piazza clicker question Lesson23 Q1

Which of these methods does a LinkedList inherit from Collection interface? Check all that apply. (section 15.1)

1. add()
2. get(int index)
3. remove(Object o)
4. removeAt(int index)
5. size()
6. list()
7. contains()
8. listIterator()

 

Activity - LinkedkList class of the Java Collections Framework

Record your participation in Piazza clicker question Lesson23 Q2

Which of these methods does a LinkedList also implement? Check all that apply. (section 15.2.2)

1. addLast
2. get(int index)
3. getFirst()
4. removeLast()
5. listIterator()

 

 

Activity - LinkedkList class of the Java Collections Framework

Record your participation in Piazza clicker question Lesson23 Q3

       LinkedList<String> flowers = new LinkedList<>();
       flowers.addFirst("petuntia");
       flowers.addFirst("poppy");
       flowers.addLast("zinnia");
       flowers.addFirst("pansy");
       flowers.add("rose");
       String myFlower = flowers.removeFirst();
       System.out.println(flowers + " " + myFlower);

Look at this code segment. Assume LinkedList has been imported. What is printed?

1. [pansy, petuntia, zinnia, rose] poppy
2. [petuntia, poppy zinnia, rose] pansy
3. [poppy, petuntia, zinnia, rose] pansy
4. nothing. There is a synax error

 

Concept - ListIterator

You use a ListIterator to access elements inside a LinkedList

To get a ListIterator, use the listIterator() method of the LinkedList class

LinkedList<String> flowers = new LinkedList<>()
...
ListIterator<String> iterator = flowers.listIterator();
  

A table of methods for ListIterator (some are inherited from Iterator)The LInkedLIst contins one element [Sally]

Concept - Manipulate the LinkedList with a ListIterator

As an example, you can remove all nodes in the list that meet a condition.

Assume you have a ListIterator called iterator

 while (iterator.hasNext())
 {
    String name = iterator.next();
    if ( some condition is met)
    {
        iterator.remove();
    }
 }

Activity - Using a ListIterator

Record your participation in Piazza clicker question Lesson23 Q4

Start with this code. You will use iterator.next() to move through the list

import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListIterator
{
   public static void main(String[] args)
   {
      // Make the list
      LinkedList<String> flowers = new LinkedList<>();
      flowers.add("rose");
      flowers.add("zinnia");
      flowers.add("pansy");
      flowers.add("petunia");
      flowers.add("daisy");
      flowers.add("California poppy");
      
      
      //put your code here
      
      //print the LinkedList
      System.out.println(flowers);
      System.out.println("Expected: [zinnia, orchid, petunia, Marigold, California poppy]");
   }
}

• get a ListIterator
• if the element is "petunia", add "marigold" after it
• replace "pansy" with "orchid"
• get a second iterator
• go through the LinkedList and remove every flower with a name of 5 or less characers.
• print the list.