Estructuras de datos lineales

Datos abstractos (ADTs) Los datos abstractos son un conjunto de objetos juntos a un conjunto de operaciones. Son abstracciones matemáticas, en su definición no se incluye ninguna forma de implementar operaciones.

Entre los datos abstractos se tienen:

• Integers
• Reals
• Booleans

Arrays

Los arrays son estructuras de datos que tienen un tamaño fijo por lo cual son muy limitados, si se quisiera aumentar su tamaño primero seria necesario crear un array más grande y pasar los datos de array original. Los datos de una array están juntos secuencial dentro de la memoria, por lo cual si se quisiera insertar un dato en medio seria necesario mover todo el array.

Matriz

Una matriz es simplemente un array de dos dimensiones o array de arrays. Esto quiere decir que se tiene un array cuyos componentes son otros arrays.

Lista enlazada

Es una estructura de datos donde cada elemento (al cual se le dice nodo) es un objeto independiente y que no tiene que estar adyacente a los demás nodos de la lista.Para enlazar los nodos, cada nodo contiene datos que referencia a otro nodo, el cual seria el siguiente nodo en la lista. El ultimo nodo siempre apunta a null, así se sabe que ya se termino de recorrer la lista. Las listas enlazadas solo se pueden recorren en una dirección.

Código

public class LinkedList {

private Node head;

private int size;

public LinkedList() {
    this.head = null;
    this.size = 0;
}
public boolean isEmpty() {
    return this.head == null;
}

public int size() {
    return this.size;
}

public void insertFirst(Object data) {
    Node newBNode = new Node(data);
    newBNode.next = this.head;
    this.head = newBNode;
    this.size++;
}
public Node deleteFirst() {
    if (this.head != null) {
        Node temp = this.head;
        this.head = this.head.next;
        this.size--;
        return temp;
    } else {
        return null;
    }
}
public void displayList() {
    Node current = this.head;
    while (current != null) {
        System.out.println(current.getData());
        current = current.getNext();
    }
}
public Node find(String searchValue) {
    Node current = this.head;
    while (current != null) {
        if (current.getData().equals(searchValue)) {
            return current;
        } else {
            current = current.getNext();
        }
    }
    return null;
}
public Node delete(String searchValue) {
    Node current = this.head;
    Node previous = this.head;

    while (current != null) {
        if (current.getData().equals(searchValue)) {
            if (current == this.head) {
                this.head = this.head.getNext();
            } else {
                previous.setNext(current.getNext());
            }
            return current;
        } else {
            previous = current;
            current = current.getNext();
        }
    }
    return null;
}

Lista doblemente enlazada

Las listas doblemente enlazadas son en esencia una lista enlazada, pero, con un puntero que apunta al nodo anterior. Esto permite que la lista se pueda recorrer en ambas direcciones por lo cual es más eficiente a la hora de buscar un dato. Sin embargo, dado que el nodo tiene dos enlaces, es más complicado borrarlo.

Código

public class DoubleEndedList {

private Node head;

private Node last;

private int size;

public DoubleEndedList() {
    this.head = null;
    this.last = null;
    this.size = 0;
}

public boolean isEmpty() {
    return this.head == this.last && this.last== null;
}

public int size() {
    return this.size;
}
public void insertFirst(Object data) {
    Node newNode = new Node(data);

    if (this.isEmpty()) {
        this.head = this.last = newNode;
    } else {
        newNode.setNext(this.head);
        this.head = newNode;
    }

    this.size++;
}

public void insertLast(Object data) {
    Node newBNode = new Node(data);

    if (this.isEmpty()) {
        this.head = this.last = newBNode;
    } else {
        this.last.setNext(newBNode);
        this.last = newBNode;
    }

    this.size++;
}

}

Listas circulares

Es como una lista enlazada normal pero el ultimo nodo no apunta a null, si no que, este apunta al primer elemento de la lista, por lo cual cada nodo siempre le esta apuntando a otro nodo. Es posible combinar este tipo e listas con listas doblemente enlazadas. Este tipo de estructuras de datos es útil cuando se necesita accesar ambos lados de la lista.

Código

public class CircularLinkedList {

private Node<E> head;
private int size = 0;

public void insertAtBeginning(E value) {
    Node<E> newNode = new Node<E>(value);
    if (head == null) {
        head = newNode;
        head.next = head;
    } else {
        Node<E> temp = head;
        temp.next = newNode;
        newNode.next = temp;
        head = newNode;
    }
    size++;
}

public void insertAtTail(E value) {
    Node<E> newBNode = new Node<E>(value);
    if (null == head) {
        head = newBNode;
        head.next = head;
    } else {
        Node<E> temp = head;
        while (temp.next != head) {
            temp = temp.next;
        }
        temp.next = newBNode;
    }
    newBNode.next = head;
    size++;
}

public void insertAtPosition(E value, int position) {
    if (position < 0 || position > size) {
        throw new IllegalArgumentException("Position is Invalid");
    }
    /* Conditions check passed, let's insert the BNode */
    Node<E> newBNode = new Node<E>(value);
    Node<E> tempBNode = head;
    Node<E> prevBNode = null;
    for (int i = 0; i < position; i++) {
        if (tempBNode.next == head) {
            break;
        }
        prevBNode = tempBNode;
        tempBNode = tempBNode.next;
    }
    prevBNode.next = newBNode;
    newBNode.next = tempBNode;
    size++;
}

public void deleteFromBeginning() {
    Node<E> temp = head;
    while (temp.next != head) {
        temp = temp.next;
    }
    temp.next = head.next;
    head = head.next;
    size--;
}

public void deleteFromPosition(int position) {
    if (position < 0 || position >= size) {
        throw new IllegalArgumentException("Position is Invalid");
    }
    Node<E> current = head, previous = head;
    for (int i = 0; i < position; i++) {
        if (current.next == head) {
            break;
        }
        previous = current;
        current = current.next;
    }
    if (position == 0) {
        deleteFromBeginning();
    } else {
        previous.next = current.next;
    }
    size--;
}

public Node<E> searchByIndex(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index is Invalid");
    }
    Node<E> temp = head;
    for (int i = 0; i < index; i++) {
        temp = temp.next;
    }
    return temp;
}

public Node<E> searchByValue(E value) {
    Node<E> temp = head;
    while (null != temp && temp.item != value) {
        temp = temp.next;
    }
    if (temp.item == value) {
        return temp;
    }
    return null;
}

public int size() {
    return size;
}

public boolean isEmpty() {
    return size == 0;
}

public void display() {
    if (head == null) {
        System.out.println("List is Empty !!");
    } else {
        Node<E> temp = head;
        while (temp.next != head) {
            System.out.println("Data at BNode = " + temp.item);
            temp = temp.next;
        }
        System.out.println("Data at BNode = " + temp.item);
    }
    System.out.println();
}

public static void main(String[] args){
    CircularLinkedList cll = new CircularLinkedList();

}

}

Pilas

En una pila solo se puede acceder a un dato al mismo tiempo, el cual es le ultimo en ser agregado. Para poder acceder a un elemento es necesario eliminar todos los elementos antes que este.

Tiene 3 métodos principales:

• Pop: Remueve el elemento de la punta de la pila, o el ultimo en ser agregado.
• Push: Agrega un elemento a la punta.
• Peek: Obtiene los datos del elemento en la punta sin eliminarlo.

Código

public class QueueList { private Node head = null; private Node tail = null;

    public void enqueue(T item) {
        Node newBNode = new Node(item);
        if (isEmpty()) {
            head = newBNode;
        } else {
            tail.next = newBNode;
        }
        tail = newBNode;
    }

    public T dequeue() {
        if (isEmpty()) {
            return null;
        }
        T item = head.getData();
        if (tail == head) {
            tail = null;
        }
        head = head.next;
        return item;
    }

    public T peek() {
        if (head == null) {
            return null;
        }
        return head.getData();
    }

    public int size() {
        int count = 0;
        for (Node node = head; node != null; node = node.next) {
            count++;
        }
        return count;
    }

    public boolean isEmpty() {
        return head == null;
    }

}

Colas

En las colas, a diferencia de las pilas, solo se puede accesar al primer elemento de la cola, el cual es el primer elemento en ser agregado. Para que poder llegar a un elemento de la cola primero es necesario elimiar todos los elementos antes que el.

Enqueue: Agrega un elemento al final de la cola Dequeue: Remueve le primer elemento de la cola Peek: Obtiene los datos del primer elemento de la cola sin eliminarlo

Código

public class StackList {

private LinkedList<T> stackList = new LinkedList();

public void push(T newElement) {
    this.stackList.insertFirst(newElement);
}

public Node<T> pop() {
    return this.stackList.deleteFirst();
}

public Node<T> peek() {
    return this.stackList.getHead();
}

public boolean isEmpty(){
    return this.stackList.isEmpty();
}

public static void main(String[] args){
    StackList stackList = new StackList();
    stackList.push("Dato1");
    stackList.push("Dato2");
    stackList.push("Dato3");

    while (!stackList.isEmpty()){
        System.out.println(stackList.pop().getData());
    }

    System.out.println("------");
}

}