寒光博客

[java] 双向链表 DoubleLinkedList
Node 增加 pre 前驱 指向上一个节点 package _09_Linear.list; /*节点*/! ...
扫描右侧二维码阅读全文
26
2019/09

[java] 双向链表 DoubleLinkedList

Node

增加 pre 前驱 指向上一个节点

package _09_Linear.list;

/*节点*/!

public class ListNode {
    Object data;//数据
    ListNode next;//指向下一个节点的指针
    ListNode pre;

    public ListNode(Object data) {//初始化构造器
        this.data = data;
    }
}

DoublLinkedList

双向链表结构
其head和tail都是空的 也就是如下定义的first和last
所有元素起于first.next 止于last

其中数据的增加
换四个linked

last.pre.next = newNode;//倒数第二个指向新的
newNode.next = last;//新的尾巴 指向 最后一个
newNode.pre = last.pre;//新的头指向 上次最后一个的前面一个
last.pre = newNode;//最后一个的头 指向新的

在删除 元素后 使得p.next p.pre =null 便于节约资源被CG清理

package _09_Linear.list;

public class DoubleLinkList implements MyList {
    private ListNode first = new ListNode(null);//head
    private ListNode last = new ListNode(null);//tail
    private int size;

    public DoubleLinkList() {//初始化两个 亚元
        first.next = last;
        last.pre = first;
    }

    /**
     * 加到 node:last 之前
     * 维护四条线
     *
     * @param element
     */
    @Override
    public void add(Object element) {
        ListNode newNode = new ListNode(element);

        last.pre.next = newNode;//倒数第二个指向新的
        newNode.next = last;//新的尾巴 指向 最后一个
        newNode.pre = last.pre;//新的头指向 上次最后一个的前面一个
        last.pre = newNode;//最后一个的头 指向新的

        size++;

    }

    @Override
    public void delete(Object element) {
        ListNode p = first.next;
        while (p != last) {//终止于 亚元
            if (p.data.equals(element)) {//当前p 匹配到了
                size--;
                p.pre.next = p.next;
                p.next.pre = p.pre;
            }
            p = p.next;//滑动指向下一个节点
        }
    }

    @Override
    public void delete(int index) {
        if (index < 0 || index >= size) {
            return;//索引超出 [0,size)
        }
        int i = 0;
        ListNode p = first.next;
        while (p != last) {
            if (i == index) {
                size--;
                p.pre.next = p.next;
                p.next.pre = p.pre;
                p.next = null;
                p.pre = null;
                break;
            }
            i++;
            p = p.next;
        }

    }

    @Override
    public void update(int index, Object newElement) {
        if (index < 0 || index >= size) {
            return;//索引超出 [0,size)
        }
        int i = 0;
        ListNode p = first.next;
        while (p != last) {
            if (i == index) {
                p.data = newElement;
                break;
            }
            i++;
            p = p.next;
        }
    }

    @Override
    public boolean contains(Object target) {
        ListNode p = first.next;
        while (p != last) {
            if (p.data.equals(target)) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public Object at(int index) {
        if (index < 0 && index >= size) {
            return null;
        }
        int i = 0;
        ListNode p = first.next;
        while (p != last) {
            if (i == index) {
                return p.data;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    @Override
    public int indexOf(Object element) {
        ListNode p = first.next;
        int i = 0;
        while (p != last) {
            if (p.data.equals(element)) {
                return i;
            }
            p = p.next;
            i++;
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode p = first.next;
        while (p != last) {
            sb.append(p.data).append(p.next != last ? "," : "");
            p = p.next;
        }
        sb.append("]");//这么写的原因是 如果为空 就[] 不然写到while 里面 while不判定就gg
        return "DoubleLinkList{" +
                "elements=" + sb.toString() +
                "size=" + size +
                '}';
    }
}

Test

package _09_Linear.list;

import org.junit.Test;

public class DoubleLinkListTest {
    DoubleLinkList list = new DoubleLinkList();


    @Test
    public void add() {
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list);
    }

    @Test
    public void delete() {
        add();
        System.out.println("deleteTest:");
        list.delete("a");
        System.out.println(list);
        list.delete("e");
        System.out.println(list);
    }

    @Test
    public void delete1() {
        add();
        System.out.println("deleteTestOfIndex:");
        list.delete(1);
        System.out.println(list);
    }

    @Test
    public void update() {
        add();
        list.update(1,'D');
        System.out.println(list);
    }

    @Test
    public void contains() {
        add();
        System.out.println(list.contains("b"));
    }

    @Test
    public void at() {
        add();
        System.out.println(list.at(4));
    }

    @Test
    public void indexOf() {
        add();
        System.out.println(list.indexOf("b"));
    }
}
本文作者:Author:     文章标题:[java] 双向链表 DoubleLinkedList
本文地址:https://dxoca.cn/dataStructure/283.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:September 26th, 2019 at 11:07 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

6 comments

  1. 寒光博客 Google Chrome 74.0.3724.8 Windows 10 中国 湖北

    把 gc写成 cg 我也是个人才 ̄﹃ ̄

  2. repostone Google Chrome 63.0.3239.132 Windows 8.1 中国 湖南

    非技术的路过。

    1. 寒光博客 Google Chrome 74.0.3724.8 Windows 10 中国 湖北
      @repostone

      ヾ(≧∇≦*)ゝ

  3. 敲代码太难了叭 QQ 8.1.3.4185 Android 9 中国 湖北
    该评论仅登录用户及评论双方可见
    1. 寒光博客 Google Chrome 74.0.3724.8 Windows 10 中国 湖北
      @敲代码太难了叭

      韬光养晦,静待时机

    2. 寒光博客 Google Chrome 74.0.3724.8 Windows 10 中国 湖北 武汉
      @敲代码太难了叭

      没有喜欢上一个人难诶~~