Data Structures and Algorithms in Java - List Data Structures

List Data Structure

• Sequential data structure: sequence of items of a given base type
• Implemented as an array/dynamic array or a linked list.
• ADT operations: getFirst(), getLast(), getNext(p), getPrev(p), get(p), set(p,x), insert(p,x), remove(p),removeFirst(), removeLast(), removeNext(p), removePrev(p), find(x),size()

Drawbacks of Arrays

• Require size information for creation.
• Inserting/deleting elements in the middle requires shifting other elements.

Self-Referential Structures

• Object that references another object of its own type.
• Used to create chains of data (e.g., linked lists, trees).

Linked Lists

• Collection of nodes storing data and links to other nodes.
• Linear data structure composed of nodes.
• Types:
  • Singly-Linked List
  • Doubly-Linked List
• Linear data structures: Array, Linked List, Stack, Queue
• Non-Linear data structures: Tree, Graph

Singly Linked Lists

• Node includes two datafields: info and next.
• 'info' stores information.
• 'next' links to the successor.
• Implementation includes methods like add(), traverse(), search(), dele(), isEmpty(), and clear().
• Operations: Inserting a new node at the beginning/end and deleting a node from the beginning/end of the list.

Circular Lists

• Nodes form a ring; the list is finite, and each node has a successor.
• Operations: Inserting nodes at the front/end.
• Applications:
  • Round-Robin Scheduling: implemented using rotate() to move the first element to the end of the list.

Doubly Linked Lists

• Each node has two reference fields: prev and next.
• Operations: Adding/Deleting a new node at the end.

Lists in java.util

• LinkedList class:
  • add(E o): Appends the specified element to the end of this list.
  • addFirst(E o): Inserts the given element at the beginning of this list.
  • addLast(E o): Appends the given element to the end of this list.
  • clear(): Removes all of the elements from this list.
  • get(int index): Returns the element at the specified position in this list.
  • getFirst(): Returns the first element in this list.
  • getLast(): Returns the last element in this list.
  • remove(int index): Removes the element at the specified position in this list.
  • removeFirst(): Removes and returns the first element from this list.
  • removeLast(): Removes and returns the last element from this list.
  • size(): Returns the number of elements in this list.
  • toArray(): Returns an array containing all of the elements in this list in the correct order.
• ArrayList class:
  • add(E o): Appends the specified element to the end of this list.
  • add(int index, E o): Inserts the given element at the specified pos.
  • clear(): Removes all of the elements from this list.
  • get(int index): Returns the element at the specified position in this list.
  • remove(int index): Removes the element at the specified position in this list.
  • size(): Returns the number of elements in this list.
  • ensureCapacity(int minCapacity): Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
  • trimToSize(): Trims the capacity of this ArrayList instance to be the list's current size.
  • toArray(): Returns an array containing all of the elements in this list in the correct order.