.. This file is part of the OpenDSA eTextbook project. See .. http://opendsa.org for more details. .. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. avmetadata:: :author: Molly Domino Lists ===== Overview & Objectives --------------------- Upon completion of this module, students will be able to: * Distinguish properties and use cases for a list from other ADT(stack, queues, bags) * Implement lists in java using an Array-Based or Linked-Chain approach * Consider various design approaches and corresponding efficiency * Trace and debug list implementations Suggested Reading: ~~~~~~~~~~~~~~~~~~ **Chapters 12 - 14: Lists, A List Implementation That Uses an Array, A List Implementation That Links Data** from `Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry `_ .. raw:: html Introduction to Lists [13:41] ----------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.1.2.1-ListIntro.pdf .. raw:: html .. admonition:: The List Interface Download to run and explore the java files (see below) from the video on your own in eclipse. .. raw:: html

ListInterface.java .. code-block:: java package list; /** * An interface for the ADT list. Entries in a list have positions that begin * with 0 * * @author Frank M. Carrano * @author Timothy M. Henry * @author maellis1 * @version July 2024 */ public interface ListInterface { /** * Adds a new entry to the end of this list. Entries currently in the list * are unaffected. The list's size is increased by 1. * * @param newEntry * The object to be added as a new entry. */ public void add(T newEntry); /** * Adds a new entry at a specified position within this list. Entries * originally at and above the specified position are at the next higher * position within the list. The list's size is increased by 1. * * @param newPosition * An integer that specifies the desired position of the new * entry. * @param newEntry * The object to be added as a new entry. * @throws IndexOutOfBoundsException * if either newPosition less than 0 or newPosition greater than * the size of the list. */ public void add(int newPosition, T newEntry); /** * Removes the entry at a given position from this list. Entries originally * at positions higher than the given position are at the next lower * position within the list, and the list's size is decreased by 1. * * @param givenPosition * An integer that indicates the position of the entry to be * removed. * @return A reference to the removed entry. * @throws IndexOutOfBoundsException * if either givenPosition less than 0 or givenPosition greater * than or equal to the size of the list. */ public T remove(int givenPosition); /** Removes all entries from this list. */ public void clear(); /** * Replaces the entry at a given position in this list. * * @param givenPosition * An integer that indicates the position of the entry to be * replaced. * @param newEntry * The object that will replace the entry at the position * givenPosition. * @return The original entry that was replaced. * @throws IndexOutOfBoundsException * if either givenPosition less than 0 or givenPosition greater * than or equal to the size of the list. */ public T replace(int givenPosition, T newEntry); /** * Retrieves the entry at a given position in this list. * * @param givenPosition * An integer that indicates the position of the desired entry. * @return A reference to the indicated entry. * @throws IndexOutOfBoundsException * if either givenPosition less than 0 or givenPosition greater * than or equal to the size of the list. */ public T getEntry(int givenPositi son); /** * Retrieves all entries that are in this list in the order in which they * occur in the list. * * @return A newly allocated array of all the entries in the list. If the * list is empty, the returned array is empty. */ public Object[] toArray(); /** * Sees whether this list contains a given entry. * * @param anEntry * The object that is the desired entry. * @return True if the list contains anEntry, or false if not. */ public boolean contains(T anEntry); /** * Gets the length of this list. * * @return The integer number of entries currently in the list. */ public int getLength(); /** * Sees whether this list is empty. * * @return True if the list is empty, or false if not. */ public boolean isEmpty(); } // end ListInterface Checkpoint 1 ------------ .. avembed:: Exercises/MengBridgeCourse/ListsCheckpoint1Summ.html ka :long_name: Checkpoint 1 .. _ListAdd: Interactive: LinkedList Add() Implementation [10:21] ---------------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.1.3.1-LinkedListAdd.pdf .. raw:: html Checkpoint 2 ------------ .. avembed:: Exercises/MengBridgeCourse/ListsCheckpoint2Summ.html ka :long_name: Checkpoint 2 Interactive: Tracing Add() with Debugger [13:33] ------------------------------------------------ .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.1.4.1-TraceAddDebugger.pdf .. raw:: html .. _ListRemove: Interactive: LinkedList Remove() [18:09] ---------------------------------------- .. admonition:: Follow Along, Practice and Explore In Eclipse, use the *Project > Download Assignment...* menu command to download the exercise project named "ex11.01-LinkedList". Refer to `01.02: Lab: LightBot for Beginners `_ if you need to review the instructions for downloading Eclipse projects. .. raw:: html

Video Slides 11.1.5.1-LinkedListRemove.pdf .. raw:: html Checkpoint 3 ------------ .. avembed:: Exercises/MengBridgeCourse/ListsCheckpoint3Summ.html ka :long_name: Checkpoint 3 Programming Practice: Lists 1 ----------------------------- .. extrtoolembed:: 'Programming Practice: Lists 1' :workout_id: 1922 .. _ListOptions: Interactive: LinkedList Details and Options [10:19] --------------------------------------------------- .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.1.7.1-LinkedListMoreDetails.pdf .. raw:: html Checkpoint 4 ------------ .. avembed:: Exercises/MengBridgeCourse/ListsCheckpoint4Summ.html ka :long_name: Checkpoint 4 .. _ListArray: Interactive: An Array Implementation of a List [15:48] ------------------------------------------------------ .. admonition:: Follow Along and Engage Download the slides corresponding to the video. Take notes on them as you watch the video, practice drawing diagrams yourself! .. raw:: html

Video Slides 11.1.8.1-ArrayListImplementation.pdf .. raw:: html Programming Practice: Lists 2 ----------------------------- .. extrtoolembed:: 'Programming Practice: Lists 2' :workout_id: 1923