Data Structures and Algorithms in Java - List Data Structures

Flashcards about List Data Structures, covering objectives, drawbacks of arrays, self-referential structures, linked lists, singly linked lists, circular lists, doubly linked lists, and lists in java.util.

What is a List?

A sequential data structure that stores a sequence of items of a given base type, where items can be added, deleted, and retrieved from any position in the list.

What are the drawbacks of using arrays?

Arrays require size information for creation; inserting or deleting elements in the middle of an array leads to moving other elements around.

What is a self-referential structure?

An object where one of its elements is a reference to another object of its own type, allowing for the creation of 'chains' of data.

What is a linked list?

A collection of nodes storing data and links to other nodes, forming a linear data structure.

What are the common types of linked lists?

Singly-Linked List and Doubly-Linked List.

What is a singly linked list?

A list where each node includes two data fields: info (to store information) and next (to link to its successor).

What is a circular list?

A list where nodes form a ring, with each node having a successor, and the list is finite.

What does the rotate() operation do in the context of circular lists and round-robin scheduling?

Moves the first element to the end of the list.

What is a doubly linked list?

A list where each node has two reference fields: one to the successor and one to the predecessor.

What does the add(E o) method do in the java.util LinkedList class?

Appends the specified element to the end of the list.

What does the addFirst(E o) method do in the java.util LinkedList class?

Inserts the given element at the beginning of this list.

What does ensureCapacity(int minCapacity) do in the java.util ArrayList class?

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.

What does trimToSize() do in the java.util ArrayList class?

Trims the capacity of this ArrayList instance to be the list's current size.