ch9

• Data structure


  A particular way of organizing data in a computer so that it can be used effectively
• Common data structures


  • Array
  • Linked List
  • Stack
  • Queue
  • Tree
  • Graph
  • Hash-table

  
• Linear data structures


  • Data elements are sequentially connected and are traversable through a single run
• Non-linear data structures


  • Data elements are hierarchically connected and are present at various levels
• Stack


  Data can only be inserted at the one end of a stack. You can only read and remove from the same end of the stack. Also known as LIFO, Last In First Out.

  
• How to create a stack in Java

  1. Import java.util.Stack

  2. Use the Stack() constructor

  3. Default Stack (any type can be mixed)

  4. Stack using Generics (E is the type of Object)
• Commonly used methods for Stack

  • push
  • pop
  • peek
  • search
  • size
  • isEmpty
  • empty
• Queue


  Queues work similarly to a line of people in a bank. The first one on the line is the first one that leaves the queue and people can only join the queue at the end. It follows the FIFO or the First-In-First-Out principle.
• How to create a queue in Java

  1. Import java.util.Queue and java.util.LinkedList

  2. Default Queue (any type can be mixed)

  3. Queue using Generics (E is the type of Object)
• Commonly used methods for Queue

  • add
  • remove
  • peek
  • size
  • isEmpty
• Linked List


  A node based data structure where the memory cells are not next to each other, but spread across different cells. Every node stores the memory address of the next node in the linked list.
• How to create a LinkedList in Java

  1. Import java.util.LinkedList

  2. Default LinkedList (any type can be mixed)

  3. LinkedList using Generics (E is the type of Object)
• Applications of linked lists

  • Implementation of stacks and queues
  • Dynamic memory allocation: linked list of free blocks
  • Implementation of graphs: Adjacency list representation
  • Maintaining directory of names
  • Performing arithmetic operations on long integers
  • Manipulation of polynomials
  • Representing sparse matrices
  • Doubly linked lists for navigation lists
  • Circular linked lists for process scheduling
• Sparse matrix contains a very few non-zero elements. When a sparse matrix is represented with a 2-dimensional array, we waste a lot of space to represent that matrix. For example, consider a matrix of size 100 X 100 containing only 10 non-zero elements. We use linked lists for this.