Java中双向链表的代码实现(2)

header = new Node(element, null, null);
            // 只有一个节点,header、tail都指向该节点
            tail = header;

} else {

// 创建新节点,新节点的pre指向原tail节点
            Node newNode = new Node(element, tail, null);
            // 让尾节点的next指向新增的节点
            tail.next = newNode;
            // 以新节点作为新的尾节点
            tail = newNode;

}
        size++;
    }

// 采用头插法为链表添加新节点
    public void addAtHeader(T element) {
        // 创建新节点,让新节点的next指向原来的header
        // 并以新节点作为新的header
        header = new Node(element, null, header);
        // 如果插入之前是空链表
        if (tail == null) {

tail = header;

}
        size++;
    }

// 删除链式线性表中指定索引处的元素
    public T delete(int index) {

if (index < 0 || index > size - 1) {

throw new IndexOutOfBoundsException("线性表索引越界");

}
        Node del = null;
        // 如果被删除的是header节点
        if (index == 0) {

del = header;
            header = header.next;
            // 释放新的header节点的prev引用
            header.prev = null;

} else {

// 获取删除节点的前一个节点
            Node prev = getNodeByIndex(index - 1);
            // 获取将要被删除的节点
            del = prev.next;
            // 让被删除节点的next指向被删除节点的下一个节点
            prev.next = del.next;
            // 让被删除节点的下一个节点的prev指向prev节点
            if (del.next != null) {

del.next.prev = prev;

}

// 将被删除节点的prev、next引用赋为null
            del.prev = null;
            del.next = null;

}
        size--;
        return del.data;
    }

// 删除链式线性表中最后一个元素
    public T remove() {

return delete(size - 1);

}

// 判断链式线性表是否为空表
    public boolean empty() {

return size == 0;

}

// 清空线性表
    public void clear() {

// 将底层数组所有元素赋为null
        header = null;
        tail = null;
        size = 0;

}

public String toString() {

// 链表为空链表
        if (empty()) {

return "[]";

} else {

StringBuilder sb = new StringBuilder("[");
            for (Node current = header; current != null; current = current.next) {

sb.append(current.data.toString() + ", ");

}
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();

}

}

// 倒序toString
    public String reverseToString() {

if (empty()) {

return "[]";

} else {

StringBuilder sb = new StringBuilder("[");
            for (Node current = tail; current != null; current = current.prev) {

sb.append(current.data.toString() + ", ");

}
            int len = sb.length();
            return sb.delete(len - 2, len).append("]").toString();

}

}

}

测试类:

package com.ietree.basic.datastructure.dublinklist;

/**
 * 测试类
 *
 * @author Dylan
 */
public class DuLinkListTest {

public static void main(String[] args) {

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/0b0834f2e041042bf6b4cc2bf7e183ea.html