LinkedList.java 3.88 KB
Newer Older
1
/*
2
 * Copyright (C) 2004-2008 Jive Software. All rights reserved.
Matt Tucker's avatar
Matt Tucker committed
3
 *
4 5 6 7 8 9 10 11 12 13 14
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
Matt Tucker's avatar
Matt Tucker committed
15 16 17 18 19 20 21 22 23 24 25
 */

package org.jivesoftware.util;


/**
 * Simple LinkedList implementation. The main feature is that list nodes
 * are public, which allows very fast delete operations when one has a
 * reference to the node that is to be deleted.<p>
 *
 * @author Jive Software
26
 * @param <E>
Matt Tucker's avatar
Matt Tucker committed
27
 */
28
public class LinkedList<E> {
Matt Tucker's avatar
Matt Tucker committed
29 30 31 32 33

    /**
     * The root of the list keeps a reference to both the first and last
     * elements of the list.
     */
34
    private LinkedListNode<E> head;
Matt Tucker's avatar
Matt Tucker committed
35 36 37 38 39

    /**
     * Creates a new linked list.
     */
    public LinkedList() {
40
    	head = new LinkedListNode<>();
Matt Tucker's avatar
Matt Tucker committed
41 42 43 44 45 46 47
    }

    /**
     * Returns the first linked list node in the list.
     *
     * @return the first element of the list.
     */
48 49
    public LinkedListNode<E> getFirst() {
        LinkedListNode<E> node = head.next;
Matt Tucker's avatar
Matt Tucker committed
50 51 52 53 54 55 56 57 58 59 60
        if (node == head) {
            return null;
        }
        return node;
    }

    /**
     * Returns the last linked list node in the list.
     *
     * @return the last element of the list.
     */
61 62
    public LinkedListNode<E> getLast() {
        LinkedListNode<E> node = head.previous;
Matt Tucker's avatar
Matt Tucker committed
63 64 65 66 67 68 69 70 71 72 73
        if (node == head) {
            return null;
        }
        return node;
    }

    /**
     * Adds a node to the beginning of the list.
     *
     * @param node the node to add to the beginning of the list.
     */
74
    public LinkedListNode<E> addFirst(LinkedListNode<E> node) {
75
    	return node.insert(head.next, head);
Matt Tucker's avatar
Matt Tucker committed
76 77 78 79 80 81 82 83 84
    }

    /**
     * Adds an object to the beginning of the list by automatically creating a
     * a new node and adding it to the beginning of the list.
     *
     * @param object the object to add to the beginning of the list.
     * @return the node created to wrap the object.
     */
85
    public LinkedListNode<E> addFirst(E object) {
86
        return new LinkedListNode<>(object, head.next, head);
87 88 89 90 91 92 93
    }

    /**
     * Adds a node to the end of the list.
     *
     * @param node the node to add to the beginning of the list.
     */
94
    public LinkedListNode<E> addLast(LinkedListNode<E> node) {
95
    	return node.insert(head, head.previous);
Matt Tucker's avatar
Matt Tucker committed
96 97 98 99 100 101 102 103 104
    }

    /**
     * Adds an object to the end of the list by automatically creating a
     * a new node and adding it to the end of the list.
     *
     * @param object the object to add to the end of the list.
     * @return the node created to wrap the object.
     */
105
    public LinkedListNode<E> addLast(E object) {
106
        return new LinkedListNode<>(object, head, head.previous);
Matt Tucker's avatar
Matt Tucker committed
107 108 109 110 111 112 113
    }

    /**
     * Erases all elements in the list and re-initializes it.
     */
    public void clear() {
        //Remove all references in the list.
114
        LinkedListNode<E> node = getLast();
Matt Tucker's avatar
Matt Tucker committed
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
        while (node != null) {
            node.remove();
            node = getLast();
        }

        //Re-initialize.
        head.next = head.previous = head;
    }

    /**
     * Returns a String representation of the linked list with a comma
     * delimited list of all the elements in the list.
     *
     * @return a String representation of the LinkedList.
     */
130 131
    @Override
	public String toString() {
132
        LinkedListNode<E> node = head.next;
133
        StringBuilder buf = new StringBuilder();
Matt Tucker's avatar
Matt Tucker committed
134 135 136 137 138 139 140
        while (node != head) {
            buf.append(node.toString()).append(", ");
            node = node.next;
        }
        return buf.toString();
    }
}