如何将元素添加到链表的末尾

Question

我正在尝试将一个元素添加到链接列表的末尾，但我不太确定如何完成此操作。这是我正在使用的方法的当前代码：

public void pushLast(T element) {
    LinearNode<T> temp = new LinearNode<T>(element);
    if (isEmpty()) {
        top = temp;
    } else {
        LinearNode<T> current = top;
        while (current.getNext() != null) {
            current = current.getNext();
        }
        current.setNext(temp);
    }

这看起来正确吗？这是我使用此方法的全部代码：

import java.lang.StringBuilder;

public class Murray_A05Q3 {

    public static void main(String[] args) {

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


        System.out.println("STACK TESTING");

        System.out.println("The stack contains:\n" + stack.toString());

        stack.push(3);
        stack.push(7);
        stack.push(4);
        System.out.println(stack.peek());
        stack.pop();        
        stack.push(9);
        stack.push(8);
        System.out.println(stack.peek());        
        System.out.println(stack.pop());
        System.out.println(stack.peek());        

        System.out.println("The size of the stack is: " + stack.size());
        System.out.println("The stack contains:\n" + stack.toString()); 

    } // End of method header.


    public static class LinkedStack<T> implements StackADT<T> {

        private int count;  
        private LinearNode<T> top; // serves as node class


     // Creating an empty stack
        public LinkedStack() {
            count = 0;
            top = null;
            int pushLast;
        }

        @Override
        public void push(T element) {
            LinearNode<T> temp = new LinearNode<T>(element);

            temp.setNext(top);
            top = temp;
            count++;
        }


        public T pop() throws EmptyCollectionException {
            if (isEmpty())
                throw new EmptyCollectionException("stack");

            T result = top.getElement();
            top = top.getNext();
            count--;

            return result;
        } 

        public void pushLast(T element) {
            LinearNode<T> temp = new LinearNode<T>(element);
            if (isEmpty()) {
                top = temp;
            } else {
                LinearNode<T> current = top;
                while (current.getNext() != null) {
                    current = current.getNext();
                }
                current.setNext(temp);
            }
        }


        public T peek() throws EmptyCollectionException {

            return top.getElement();    
        }


        public boolean isEmpty() {

            return (top == null);   
        }


        public int size() {

            return count;
        }


        public String toString() {


            if (isEmpty()) {
                return " ";
            }

            StringBuilder sb = new StringBuilder(top.toString());
            LinearNode<T> next = top.getNext();

            while(next != null) {
                sb.append("\n").append(next.getElement());
                next = next.getNext();

            }

            return sb.toString();

        } // End of the toString method.

    } // End of method header.

} // End of class header.

注意：以防万一你想运行这个自己，我提供了三个文件附加到上面的文件。

线性节点：

public class LinearNode<T> {
    private LinearNode<T> next;
    private T element;

    public LinearNode() {
        next = null;
        element = null;
    }

    public LinearNode(T elem) {
        next = null;
        element = elem;
    }

    public LinearNode<T> getNext() {
        return next;
    }

    public void setNext(LinearNode<T> node) {
        next = node;
    }

    public T getElement() {
        return element;
    }


    public void setElement(T elem) {
        element = elem;
    }
}

空集合异常：

public class EmptyCollectionException extends RuntimeException {

    public EmptyCollectionException(String collection) {
        super("The " + collection + " is empty.");
    }
}

谢谢！

Answer 1

当堆栈列表中有项目时添加数据项后，您不会重置数据结构的当前成员，因此您可能会在 peek().添加第一项时，您似乎也没有重置 current 节点。试试这个：

编辑：我想我是在太累的时候才回答这个问题的，而且是不正确的。

Answer 2

我假设这只是一个了解链表内部工作原理的学习练习，否则，请参阅上面 Alex Taylor 的建议。

您的方法会奏效，但列表越长，速度就会越慢。如果您的 class 维护对列表中最后一个元素的引用，您可以推进一个 O(1) 的步骤，而不是在追加之前访问列表中的每个元素 O(N)。

另一件需要考虑的事情是保护您的对象不被并发使用。如果两个线程在同一个对象上同时使用运行您的 pushLast 方法，那么它们都可以确定列表中与 current 相同的最后一个成员，并且一个可以覆盖另一个的next 值，丢失数据。在 Java 手册中查找 synchronized。

如何将元素添加到链表的末尾

How to add an element to the end of a linked list

java

stack

list