CS102 · Linked Lists · Annotated SlidesLinked Lists
Original
Overview

Linked Lists

Linked data structures, the generic LinkedList<E> class and its operations, iterators, sorting a LinkedList with a Comparator, and PriorityQueue.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 24 slides
  1. 1 Slide 1
  2. 2 The Class LinkedList
  3. 3 For example the following statement creates myList as a list
  4. 4 Linked Lists
  5. 5 Slide 5
  6. 6 The LinkedList Class
  7. 7 LinkedList
  8. 8 LinkedList
  9. 9 LinkedList (cont.)
  10. 10 Iterators
  11. 11 Iterators
  12. 12 Iterator Java Interface
  13. 13 Program: How to add all elements of a list to
  14. 14 Description:
  15. 15 Program: How to copy LinkedList to array?
  16. 16 Description:
  17. 17 This example gives you how to sort a LinkedList using Comparator. The LinkedList contains user defined objects. By using Collections.sort method you can sort the LinkedList. You have to pass Comparator object which contains your sort logic. The example sorts the Empl objects based on highest salary.
  18. 18 Check Full Code: EmplComp
  19. 19 import java.util.LinkedList;
  20. 20 Slide 20
  21. 21 Priority Queue Class
  22. 22 peek(): The peek() method is used to look at the front
  23. 23 !"! // Check code PriorityQueueTest.java ! !#! // Standard library class PriorityQueue test program. ! !$! import java.util.PriorityQueue;
  24. 24 Student Priority Queue Demo
Slide 1 / 24

Slide 1

Slide 1: Slide 1
Slide 2 / 24

The Class LinkedList

Slide 2: The Class LinkedList

Notes

  1. A linked structure: nodes holding data and a reference to the next node.

Slide 3 / 24

For example the following statement creates myList as a list

Slide 3: For example the following statement creates myList as a list
Slide 4 / 24

Linked Lists

Slide 4: Linked Lists

Notes

  1. Dynamic: grows and shrinks one node at a time; no fixed size.

Exam angle

PredictionQ1

Compared with ArrayList, LinkedList is better at:

Slide 5 / 24

Slide 5

Slide 5: Slide 5
Slide 6 / 24

The LinkedList Class

Slide 6: The LinkedList Class
Slide 7 / 24

LinkedList

Slide 7: LinkedList
Slide 8 / 24

LinkedList

Slide 8: LinkedList

Notes

  1. Methods: add, addFirst, addLast, getFirst, getLast, removeFirst, removeLast, get, size.

Exam angle

PredictionQ1

Which method inserts at the front of a LinkedList?

Slide 9 / 24

LinkedList (cont.)

Slide 9: LinkedList (cont.)
Slide 10 / 24

Iterators

Slide 10: Iterators

Notes

  1. Iterators traverse the list: hasNext(), next(); ListIterator goes both ways.

Slide 11 / 24

Iterators

Slide 11: Iterators
Slide 12 / 24

Iterator Java Interface

Slide 12: Iterator Java Interface
Slide 13 / 24

Program: How to add all elements of a list to

Slide 13: Program: How to add all elements of a list to
Slide 14 / 24

Description:

Slide 14: Description:
Slide 15 / 24

Program: How to copy LinkedList to array?

Slide 15: Program: How to copy LinkedList to array?
Slide 16 / 24

Description:

Slide 16: Description:
Slide 17 / 24

This example gives you how to sort a LinkedList using Comparator. The LinkedList contains user defined objects. By using Collections.sort method you can sort the LinkedList. You have to pass Comparator object which contains your sort logic. The example sorts the Empl objects based on highest salary.

Slide 17: This example gives you how to sort a LinkedList using Comparator. The LinkedList contains user defined objects. By using Collections.sort method you can sort the LinkedList. You have to pass Comparator object which contains your sort logic. The example sorts the Empl objects based on highest salary.
Slide 18 / 24

Check Full Code: EmplComp

Slide 18: Check Full Code: EmplComp
Slide 19 / 24

import java.util.LinkedList;

Slide 19: import java.util.LinkedList;
Slide 20 / 24

Slide 20

Slide 20: Slide 20
Slide 21 / 24

Priority Queue Class

Slide 21: Priority Queue Class
Slide 22 / 24

peek(): The peek() method is used to look at the front

Slide 22: peek(): The peek() method is used to look at the front
Slide 23 / 24

!"! // Check code PriorityQueueTest.java ! !#! // Standard library class PriorityQueue test program. ! !$! import java.util.PriorityQueue;

Slide 23: !"! // Check code PriorityQueueTest.java ! !#! // Standard library class PriorityQueue test program. ! !$! import java.util.PriorityQueue;

Notes

  1. PriorityQueue: poll() always returns the smallest (highest-priority) element.

Exam angle

PredictionQ1

A PriorityQueue<Integer> holding 5, 1, 3: poll() returns:

Slide 24 / 24

Student Priority Queue Demo

Slide 24: Student Priority Queue Demo