Data Structures & Algorithms

Array

An array is a sequenced collection of variables all of the same type. Each variable, or cell, in an array has an index, which uniquely refers to the value stored in that cell. The cells of an array, A, are numbered 0, 1, 2, and so on. Each value stored in an array is often called an element of that array.

• An array can store primitive elements, such as characters.
• An array can also store references to objects.

• Adding an Entry:
  • To add an entry e into array board at index i, we need to make room for it by shifting forward the n - i entries board[i],...,board[n - 1]

• Removing an Entry:
  • To remove the entry e at index i, we need to fill the hole left by e by shifting backward the n - i - 1 elements board[i + 1],...,board[n - 1]

List ADT

https://www.youtube.com/watch?v=HdFG8L1sajw

List as Abstract Data Type. Cuando hablamos de ADT, queremos simplemente definir el comportamiento de la estructura de datos que queremmos; y no la definición estricta de una implementación en programación. Por tanto, en este sentido, a List ADT sería:

• A way to organize data
  • Examples
    • To-do list
    • Gift lists
    • Grocery Lists
• Items in list have position
• Items may be added anywhere
  • Write/modify items at a position.

Array Lists

An obvious choice for implementing the list ADT is to use an array, A, where A[i] stores (a reference to) the element with index i. With a representation based on an array A, the get(i) and set(i, e) methods are easy to implement by accessing A[i] (assuming i is a legitimate index).

• Adding an Entry:
  • As we already saw on Arrays, in an operation add(i,o), we need to make room for the new element by shifting forward the n - i elements A[i],..., A[n - 1]
  • In the worst case (i = 0), this takes Order n time [O(n) times]
  • In an add operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one.

• Removing an Entry:
  • In an operation remove(i), we need to fill the hole left by the removed element by shifting backward the n - i - 1 elements A[i + 1],..., A[n - 1]
  • In the worst case (i = 0), this takes O(n) time

• Performance:
  • In an array-based implementation of a dynamic list:
    • The space used by the data structure is O(n)
    • Indexing the element at i takes O(1) time
    • add and remove run in O(n) time

Single-Linked Lists

• A singly linked list is a concrete data structure consisting of a sequence of nodes, starting from a head pointer.
• Each node stores
  • Element or data
  • Link (reference or address) to the next node

• The ArrayList is limited because its add and remove methods operate in linear (O(n)) time—requiring a loop to shift elements.
• A linked list is useful for inserting and removing at arbitrary locations
  • In a linked list, instead of an index, each element is linked to the following element
  • A linked list can add and remove elements at a known location in O(1) time

Implementing a Single-Linked List in Java

NodeInterface.java

// Data Structures and Algorithms
// CCT College Dublin
// Dr. Muhammad Iqbal

public interface NodeInterface <E> {
    public void addFirst(E item);
    public void addAfter(Node<E> node, E item);
    public E removeFirst();
    public E removeAfter(Node<E> node);
    public Node<E> getNode(int index);
    public E get(int index);
    public E set(int index, E newValue);
    public void add(int index, E item);
    public boolean add(E item);
    public E remove(int index);
    public boolean remove(E item);
    public int size();
}

Node.java

// Data Structures and Algorithms
// CCT College Dublin
// Dr. Muhammad Iqbal


public class Node<E> {

    /** The data value. */
    public E data;
    /** The link */
    public Node<E> next = null;

    /**
     * Construct a node with the given data value and link
     * @param data - The data value 
     * @param next - The link
     */
    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }

    /**
     * Construct a node with the given data value
     * @param data - The data value 
     */
    public Node(E data) {
        this(data, null);
    }
}

SingleLinkedList.java

// Data Structures and Algorithms
// CCT College Dublin
// Dr. Muhammad Iqbal

public class SingleLinkedList<E> implements NodeInterface<E> {

    public Node<E> head = null;
    /** The size of the list */
    private int size = 0;

    // Helper Methods
    /** Insert an item as the first item of the list.
     *	@param item The item to be inserted
     */
    public void addFirst(E item) {
        head = new Node<E>(item, head);
        size++;
    }

    /**
     * Add a node after a given node
     * @param node The node which the new item is inserted after
     * @param item The item to insert
     */
    public void addAfter(Node<E> node, E item) {
        node.next = new Node<E>(item, node.next);
        size++;
    }

    /**
     * Remove the first node from the list
     * @returns The removed node's data or null if the list is empty
     */
    public E removeFirst() {
        Node<E> temp = head;
        if (head != null) {
            head = head.next;
        }
        if (temp != null) {
            size--;
            return temp.data;
        } else {
            return null;
        }
    }

    /**
     * Remove the node after a given node
     * @param node The node before the one to be removed
     * @returns The data from the removed node, or null
     *          if there is no node to remove
     */
    public E removeAfter(Node<E> node) {
        Node<E> temp = node.next;
        if (temp != null) {
            node.next = temp.next;
            size--;
            return temp.data;
        } else {
            return null;
        }
    }

    /**
     * Find the node at a specified index
     * @param index The index of the node sought
     * @returns The node at index or null if it does not exist
     */
    public Node<E> getNode(int index) {
        Node<E> node = head;
        for (int i = 0; i < index && node != null; i++) {
            node = node.next;
        }
        return node;
    }

    // Public Methods
    /**
     * Get the data value at index
     * @param index The index of the element to return
     * @returns The data at index
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(Integer.toString(index));
        }
        Node<E> node = getNode(index);
        return node.data;
    }

    /**
     * Set the data value at index
     * @param index The index of the item to change
     * @param newValue The new value
     * @returns The data value priviously at index
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public E set(int index, E newValue) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(Integer.toString(index));
        }
        Node<E> node = getNode(index);
        E result = node.data;
        node.data = newValue;
        return result;
    }

    /**
     * Insert the specified item at the specified position in the list.
     * Shifts the element currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indicies)
     * @param index Index at which the specified item is to be inserted
     * @param item The item to be inserted
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public void add(int index, E item) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(Integer.toString(index));
        }
        if (index == 0) {
            addFirst(item);
        } else {
            Node<E> node = getNode(index - 1);
            addAfter(node, item);
        }
    }

    /**
     * Append the specified item to the end of the list
     * @param item The item to be appended
     * @returns true (as specified by the Collection interface)
     */
    public boolean add(E item) {
        add(size, item);
        return true;
    }

    /*<exercise chapter="2" section="5" type="programming" number="1">*/
    /**
     * Remove the item at the specified position in the list. Shifts
     * any squsequent items to the left (subtracts one from their
     * indicies). Returns the tiem that was removed.
     * @param index The index of the item to be removed
     * @returns The item that was at the specified position
     * @throws IndexOutOfBoundsException if the index is out of range
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(Integer.toString(index));
        }
        Node<E> removedNode = null;
        if (index == 0) {
            return removeFirst();
        } else {
            Node<E> node = getNode(index - 1);
            return removeAfter(node);
        }
    }
    /*</exercise>*/

    /**
     * Query the size of the list
     * @return The number of objects in the list
     */
    public int size() {
        return size;
    }

    /**
     * Obtain a string representation of the list
     * @return A String representation of the list 
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node p = head;
        if (p != null) {
            while (p.next != null) {
                sb.append(p.data.toString());
                sb.append(" ==> ");
                p = p.next;
            }
            sb.append(p.data.toString());
        }
        sb.append("]");
        return sb.toString();
    }

    /*<exercise chapter="2" section="5" type="programming" number="3">*/
    /**
     * Remove the first occurence of element item.
     * @param item The item to be removed
     * @return true if item is found and removed; otherwise, return false.
     */
    public boolean remove(E item) {
        if (head == null) {
            return false;
        }
        Node<E> current = head;
        if (item.equals(current.data)) {
            removeFirst();
            return true;
        }
        while (current.next != null) {
            if (item.equals(current.next.data)) {
                removeAfter(current);
                return true;
            }
            current = current.next;
        }
        return false;
    }
}

SLLTest.java

// Data Structures and Algorithms
// CCT College Dublin
// Dr. Muhammad Iqbal


public class SLLTest {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Node<String> tom = new Node<String>("Tom");
        Node<String> dick = new Node<String>("Dick");
        Node<String> harry = new Node<String>("Harry");
        Node<String> sam = new Node<String>("Sam");

        tom.next = dick;
        dick.next = harry;
        harry.next = sam;
        
        SingleLinkedList<String> testInstance = new SingleLinkedList<String>();
        testInstance.add("Tom");
        testInstance.add("Dick");
        testInstance.add("Harry");
        testInstance.add("Berry");
        testInstance.add(4, "Peter");
        
        for (int i = 0; i < testInstance.size(); i++)
           {
             System.out.println("Linked List Values are " + testInstance.get(i));
           }
        
        testInstance.remove("Harry");
        testInstance.remove(1);
        testInstance.removeFirst();
        testInstance.toString();
        System.out.println("Linked List Values are " + testInstance.toString());
        
    for (int i = 0; i < testInstance.size(); i++)
        {
            System.out.println("Value are " + testInstance.get(i));
        }
        
    }
    
}