10.4. Destructive Linked Lists

The Java LinkedList class

---

The List class is similar in spirit to the Java String class; you can create new lists, but you cannot change an existing list. The Java java.util.LinkedList class provides a class of linked lists with destructive operations. That is, they change an existing list.

A LinkedList can have items of any desired type, as long as the type is a class, not a primitive type. Instances of type LinkedList<T> are linked lists of things of type T. For example, LinkedList<String> is a type of linked lists of strings. Type LinkedList<int> is not allowed because int is a primitive type, but LinkedList<Integer> is allowed.

The following are some of the supported operations.

• new LinkedList<T>() yields a new empty list.

• L.size() returns the number of members of L.

• L.addFirst(x) adds x to the beginning of linked list L.

• L.addLast(x) adds x to the end of linked list L.

• L.getFirst() returns the first member of list L.

• L.getLast() returns the last member of list L.

• L.contains(x) is true if x occurs in linked list L.

• L.push(x) adds x to the beginning of L.

• L.pop() removes and returns the first member of L.

• L.peek() is the same as L.getFirst().

• L.get(k) returns the k-th value in list L, indexing from 0.

• L.set(k,x) changes the k-th member of L to x, and returns the previous k-th member of L. Indexing is from 0.

Example

---

You can use a linked list as a stack, where you can add something to the top of the stack and you can remove the top. This section demonstrates a stacks. It defines a tool eval.eval(s), which evaluates an expression s (a string) that uses real numbers, binary operators +, −, * and /, and parentheses, where + and − have low precedence and * and / have higher precedence. Because of the simple scanner used, it requires spaces between adjacent things. For example,

  double x = eval.eval("2 * ( 5.1 + 2 )");

The algorithm works as follows. It keeps two stacks, the data stack and the operator stack. The data stack represents numbers that have occurred in the expression or that are the values of subexpressions. The operator stack holds operators that are waiting to be performed. An operator always works on the top two numbers on the data stack, and replaces those two numbers by their result. For example, if the data stack holds (from top to bottom) [2, 5, 9] and the operator stack holds [*, +], then these stacks represent expression (2*5) + 9. That result would be computed by popping the 2 and 5 and pushing 2*5 = 10. After that, the data stack holds [10, 9] and the operator stack holds [+]. Now the addition is performed, leaving the data stack holding [19] and the operator stack empty.

The point of having these stacks is to handle precedence. We scan the expression from left to right. Any time a number is seen, it is pushed onto the data stack. When an operator op is seen, first all higher and equal precedence operators on the operator stack are performed, until the operator stack is either empty or its top has lower precedence than op. Then op is pushed onto the operator stack.

Parentheses are handled as follows. When a left parenthesis is seen, it is pushed onto the operator stack. A left parenthesis is treated like a very low precedence operator. When a right parenthesis is seen, operators are popped and performed until the matching left parenthesis is seen. Then the left parenthesis is popped.

The following demonstrates evaluation of expression "2 * ( 3 + 4 * 5 + 6 ) + 7 * 8". At each step, the stacks and the remainder of the expression is shown. Stacks are shown top to bottom.

Here is the implementation in Java.

import java.util.LinkedList;
import java.util.Scanner;
import static java.lang.Character.*;

/** Class eval provides static method eval(e) that evaluates
    a simple expression e.
*/

public class eval
{

    //----------------------------------------------------------
    //                     eval(e)
    //----------------------------------------------------------
    /** eval(e) yields the value of expression e.
        
        @param e An expression with real constants,
                 operators +, -, *, / and parentheses, with spaces
                 between tokens.
        
         @return The value of the expression.

         @throws ExpressionException(e) 
                 on a poorly formed expression e.
    */
    //----------------------------------------------------------

    public static double eval(String e)
    {
        LinkedList<Double>    datastk  = new LinkedList<Double>();
        LinkedList<Character> opstk    = new LinkedList<Character>();
        Scanner               s        = new Scanner(e);
        
        while(s.hasNext()) {
            String tok   = s.next();
            char   tokch = tok.charAt(0);

            //------------------------------------
            // A number goes onto the data stack.
            //------------------------------------

	    if(isDigit(tokch)) {
                datastk.push(Double.valueOf(tok));                
            }

            //------------------------------------
            // Error check: Other tokens have length 1.
            //------------------------------------

            else if(tok.length() != 1) {
               throw new ExpressionException(e);
            }

            //------------------------------------
            // Push '(' onto the operator stack.
            //------------------------------------

            else if(tokch == '(') {
                opstk.push('(');
            }

            //------------------------------------
            // At ')', perform operations that are
            // waiting on the operator stack until
            // the matching '(' is found.  Then
            // pop ')' from the operator stack.
            //------------------------------------

            else if(tokch == ')') {
                while(opstk.size() > 0 && opstk.peek() != '(') {
                    performOp(opstk.pop(), datastk, e);
                }
                if(opstk.size() == 0) {
                    throw new ExpressionException(e);
                }
                else {
                    opstk.pop();
                }
            }

            //------------------------------------
            // At an operator, perform all operators
            // on the operator stack that have the
            // same or higher precedence.  Then
            // push this operator onto the operator
            // stack.
            //------------------------------------

            else {
                while(opstk.size() != 0 && !shouldDelay(opstk.peek(), tokch, e)) {
                     performOp(opstk.pop(), datastk, e);
                }
                opstk.push(tokch);
            }
        }

        //------------------------------------
        // At the end of the string, perform all
        // operators on the operator stack.
        //------------------------------------

        while(opstk.size() > 0) {
            performOp(opstk.pop(), datastk, e);
        }

        //------------------------------------
        // The expression's value is sitting
        // on the data stack.
        //------------------------------------

        if(datastk.size() != 1) {
            throw new ExpressionException(e);
        }
        else {
            return datastk.pop();
        }
    }

    //----------------------------------------------------------
    //                 shouldDelay(stkop, tokop, e)
    //----------------------------------------------------------
    /** Determine if an operator should be performed now or
        delayed.
        <p>
        The operator stack has stkop on its top, and we have just
        read tokop.  Return false if we should perform the operation
        on the stack now, true if we should delay it until later.

        @param stktop The operator on top of the operator stack.
        @param tokop  The operator that was just read.
        @param e      The full expression, for exceptions.
 
        @throws ExceptionExpression(e)
                if either operator is not one of the supported operators.
    */
    //----------------------------------------------------------

    private static boolean shouldDelay(char stkop, char tokop, String e)
    {
        return stkop == '(' || precedence(stkop, e) < precedence(tokop, e);
    }

    //----------------------------------------------------------
    //                   precedence(op, e)
    //----------------------------------------------------------
    /** Return the precedence of operator op.

        @param e  The full expression, used for exceptions

        @param op The operator

        @throws ExpressionException(e)
                if op is not one of the supported operators
    */
    //----------------------------------------------------------

    private static int precedence(char op, String e)
    {
        if(op == '+' || op == '-') {
            return 1;
        }
        if(op == '*' || op == '/') {
            return 2;
        }
        if(op == '(') {
            return 3;
        }
        else {
            throw new ExpressionException(e);
        }
    }
        
    //----------------------------------------------------------
    //                        performOp(op, datastk, e)
    //----------------------------------------------------------
    /** Pop the top two numbers y and x from datastk,
        where y is above x.  Push op(x,y) onto datastk,
        the result of performing operator op on parameters
        x and y.

        @param op      The operator to perform.
        @param datastk The data stack object.
        @param e       The full expression, for exceptions.
       
        @throws ExpressionException(e)
                if op is not one of the supported operators or 
                if datastk does not have at least two values in it.
    */
    //----------------------------------------------------------

    private static void performOp(char op, LinkedList<Double> datastk, String e)
    {
        if(datastk.size() < 2) {
            throw new ExpressionException(e);
        }
        else {
            double y = datastk.pop();
            double x = datastk.pop();
            datastk.push(doOp(op, x, y, e));
        }
    }

    //----------------------------------------------------------
    //                   doOp
    //----------------------------------------------------------
    /** Return op(x,y), the result of performing operator op on
        x and y.  For example if op is '-' then return x - y.

        @param op The operator
        @param x  The left-hand operand
        @param y  The right-hand operand
        @param e  The entire expression, for exceptions.
       
        @throws ExpressionException(e) 
                if op is not one of the supported operators.
    */
    //----------------------------------------------------------

    private static double doOp(char op, double x, double y, String e)
    {
        switch(op) {
        case '+':
            return x + y;

        case '-':
            return x - y;

        case '*':
            return x * y;

        case '/':
            return x / y;

        default:
            throw new ExpressionException(e);
        }
    }
}

//=======================================================

class ExpressionException extends RuntimeException
{
    public String expr;

    public ExpressionException(String e)
    {
        expr = e;
    }

    public String toString()
    {
        return "ExpressionException(\"" + expr + "\")";
    }
}