LAB 10

First we need a class node

15 min

    Class Node{

        int value;
        Node next;

        Node (int val){
            value = val
            node  = NULL
        }

        Node (int val, Node next){
            value = val 
            this.next  = next
        }

    }

30 mins

    Class List{

        Node head;

        boolean isEmpty(){
            return Head == null
        }

        int length(){

            int len = 0;

            Node node = head;
            while( node.next != NULL )
                len++

            return len;
        }


        // creates a new node with the integer and adds it to the end of the list;
        void addAsTail(int i){

            Node node = new Node (i, null);

            Node current = head
            while current.next != null
                current = current.next

            current.next = node

        }

        // creates a new node with the integer and adds it behind all nodes with a val less or equal the val of the node, possibly at the end of the list;
        void addSorted(int i){

            Node node = new Node (i, null);

            // first check if the list is empty

            if this.empty()
                head = node;

            // the list is not empty then iterate to find the right place 

            Node current = head
            while current.next != null && current.value <= i
                current = current.next

            if current.next == null
                current.next = node

            else
                // show picture
                Node tmp = current.next
                current.next = node 
                node.next = tmp
        }

        // reverses the list;
        void reverse() {

            // 

            Node node = head;

            List list = new List()

            while node.next != null
                newnode = new Node(node) // deep copy
                list.addFirst(node)
                node = node.next

        }

        int popHead(){

            if head==null
                return "error"

            else
                int value = head.value
                head = head.next
                return value

        }

        void removeFirst (int i){

            Node current = head
            while current.next != null && current.value != i
                current = current.next

            if current.next == null
                return
            else
                // bridge

        }


    }

Head Tail list

Class HTList{

    Node head;
    Node tail;
    ...

    How some method change... lets try
}

Do you want that we implement any specific method

15 mins

    // void insertionSort()        
      public void insertSorted(Node node) {
        if (head == null) {
            head = node;
            node.next = null;
        } else if (node.val < head.val) {
            node.next = head;
            head = node;
        } else {
            Node p = head;
            int v = node.val;
            while (p.next != null && p.next.val <= v) {
                p = p.next;
            }
            // insert new node after p
            node.next = p.next;
            p.next = node;
        }
    }

15 min

    void public static quickSort (HTList list)

        // base case

        // partition
        HTList llist = new HTList();
        HTList rlist = new HTList();

        HTNode pivot = list.pop

        HTNode current = list.head

        while current.next != null

            HTNode newcurrent = HTNode( current )

            if newcurrent.value<pivot.value

                    llist.add(newcurrent)

            else 
                    rlist.add(newcurrent)


        rlist.add(pivot)

        quickSort(llist)
        quickSort(rlist)

        list = llist.append(rlist)


        return list

3. Quick sort

public void quickSort() {
        if (this.length() <= 1) {
            return this;
        } else {
            HTList Ls = new HTList(null);
            HTList Bs = new HTList(null);
            Node pivot = this.popHead();
            int pivotVal = pivot.val;
            Node p = this.head;
            Node pNext = null;
            while (p != null) {
                pNext = p.next;
                if (p.val < pivotVal) {
                    Ls.insertHead(p);
                } else {
                    Bs.insertHead(p);
                }
                p = pNext;
            }
            Ls.quickSort();
            Bs.quickSort();
            Bs.insertHead(pivot);
            Ls.append(Bs);
            this.head = Ls.head;
            this.tail = Ls.tail;

        }
    }