Skip to content

Instantly share code, notes, and snippets.

@technoglot
Created May 1, 2019 01:48
Show Gist options
  • Save technoglot/ffcf8ddfa023518f4bf1fcf64044a641 to your computer and use it in GitHub Desktop.
Save technoglot/ffcf8ddfa023518f4bf1fcf64044a641 to your computer and use it in GitHub Desktop.
Collection of common data structures implemented in Java.
import java.util.Stack;

public class Stack {

    public static void main(String[] args) {

        Stack<Integer> stack = new Stack<Integer>();

        push(stack);
        push(stack);
        pop(stack);
        peek(stack);
        search(stack, 6);
        remove(stack, 5);

    }

    public static void push(Stack<Integer> stack) {
        for (int i = 0; i < 10; i++) {
            stack.push(i);
        }
    }

    public static void pop(Stack<Integer> stack) {

        for (int i = 0; i < 10; i++) {
            Integer x = (Integer) stack.pop();
        }
        System.out.println("Pop: " + stack);
    }

    public static void peek(Stack<Integer> stack) {
        System.out.println("Top of the stack: " + stack.peek());
    }

    public static void search(Stack<Integer> stack, int a) {
        Integer b = (Integer) stack.search(a);

        if (b == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element is at position: " + b);
        }
    }

    public static void remove(Stack<Integer> stack, int i) {
        System.out.println("Item removed: " + stack.remove(i));

        System.out.println("Pop: " + stack);
    }

}
package linkedlist;

public class LinkedList {
    // reference to the head node.
    private Node head;
    private int listCount;

    // LinkedList constructor
    public LinkedList() {
        // this is an empty list, so the reference to the head node
        // is set to a new node with no data
        head = new Node(null);
        listCount = 0;
    }

    public void add(Object data) {
        // post: appends the specified element to the end of this list.
        Node temp = new Node(data);
        Node current = head;
        
        // starting at the head node, crawl to the end of the list
        while (current.getNext() != null) {
            current = current.getNext();
        }
        
        // the last node's "next" reference set to our new node
        current.setNext(temp);
        listCount++; // increment the number of elements variable
    }

    public void add(Object data, int index) {
        // post: inserts the specified element at the specified position in this list.
        Node temp = new Node(data);
        Node current = head;
        
        // crawl to the requested index or the last element in the list,
        // whichever comes first
        for (int i = 1; i < index && current.getNext() != null; i++) {
            current = current.getNext();
        }
        // set the new node's next-node reference to this node's next-node reference
        temp.setNext(current.getNext());
        // now set this node's next-node reference to the new node
        current.setNext(temp);
        listCount++;// increment the number of elements variable
    }

    public Object get(int index) {
        // post: returns the element at the specified position in this list.
    
        // index must be 1 or higher
        if (index <= 0) {
            return null;
        }

        Node current = head.getNext();
        for (int i = 1; i < index; i++) {
            if (current.getNext() == null) {
                return null;
            }

            current = current.getNext();
        }
        return current.getData();
    }

    public boolean remove(int index) {
        // post: removes the element at the specified position in this list.
    
        // if the index is out of range, exit
        if (index < 1 || index > size()) {
            return false;
        }

        Node current = head;
        for (int i = 1; i < index; i++) {
            if (current.getNext() == null) {
                return false;
            }

            current = current.getNext();
        }
        current.setNext(current.getNext().getNext());
        listCount--; // decrement the number of elements variable
        return true;
    }

    public void print() {
        Node tnode = head;
        while (tnode != null) {
            System.out.print(tnode.data + " ");
            tnode = tnode.next;
        }
    }
    
    public int size() // post: returns the number of elements in this list.
    {
        return listCount;
    }

    @Override
    public String toString() {
        Node current = head.getNext();
        String output = "";
        while (current != null) {
            output += "[" + current.getData().toString() + "]";
            current = current.getNext();
        }
        return output;
    }

    private class Node {
        // reference to the next node in the chain,
        // or null if there isn't one.

        Node next;
        // data carried by this node.
        // could be of any type you need.
        Object data;

        // Node constructor
        public Node(Object _data) {
            next = null;
            data = _data;
        }

        // another Node constructor if we want to
        // specify the node to point to.
        public Node(Object _data, Node _next) {
            next = _next;
            data = _data;
        }

        // these methods should be self-explanatory
        public Object getData() {
            return data;
        }

        public void setData(Object _data) {
            data = _data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node _next) {
            next = _next;
        }
    }
    
    public static void main(String[] args) {
        //Create a LinkedList reference variable
         LinkedList list = new LinkedList();
         
        //Assignment 1
        //Add values to the LinkedList
        list.add(25);
        list.add(52);
        list.add(4);
        list.add(79);
        list.add(23);
        list.add(80);
        list.add(77);
        list.add(54);
        list.add(45);
        list.add(11);
        
        //Print list contents and size
        list.print();
        System.out.println("");
        System.out.println(list.size());
        
        //Add these values at the end of the list
        list.add(5);
        list.add(100);
        list.add(27);
        list.add(25);
        list.add(45);
        list.add(1);
        list.add(4);
        list.add(2);
        list.add(9);
        list.add(33);
        
        //Print list contents and size
        list.print();
        System.out.println("");
        System.out.println(list.size());
        
        //Assignment 2
        list.print();
        System.out.println("");
        
        list.remove(20);
        list.print();
        System.out.println("");
        
        list.remove(19);
        list.print();
        System.out.println("");
        
        list.remove(18);
        list.print();
        System.out.println("");
        
        list.remove(17);
        list.print();
        System.out.println("");
        
        System.out.println(list.size());
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment