美文网首页
数据结构-双链表(java)

数据结构-双链表(java)

作者: 鼬殿 | 来源:发表于2020-05-11 16:14 被阅读0次

简介:
双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱

链表的设计

代码实现

package com.njf;

public class DoublyLinkedList<E> {
    /**
     * 链表大小
     */
    private int size;
    /**
     * 指向头结点的引用
     */
    private Node<E> first;
    /**
     * 指向尾结点的引用
     */
    private Node<E> last;
    
    private static final int ELEMENT_NOT_FOUND = -1;
    
    private static class Node<E> {//创建节点
        //数据域
        E element;
        //指向前结点的引用
        Node<E> prev;
        //指向后继结点的引用
        Node<E> next;
        public Node(Node<E> prev,E element, Node<E> next) {//构造函数
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
        
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            if (prev != null) {
                sb.append(prev.element);
            } else {
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if (next != null) {
                sb.append(next.element);
            } else {
                sb.append("null");
            }
            return sb.toString();
        }
    }
    
    /**
     *  获取index位置对应的节点对象
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        if (index < (size>>1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
    
    /**
     * 清除所有链表数据
     */
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    /**
     * 链表大小
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 链表是否为空
     * @return
     */
    public boolean isEmpty() {
         return size == 0;
    }

    /**
     * 是否包含某个数据元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加节点到尾部
     * @param element
     */
    public void add(E element) {
        add(size, element);
    }

    /**
     * 获取index位置的节点中的数据
     * @param index
     * @return
     */
    public E get(int index) {
        return node(index).element;
    }

    /**
     * 设置index位置节点中的数据
     * @param index
     * @param element
     * @return 原来的节点中的数据
     */
    public E set(int index, E element) {
        //获取当前节点
        Node<E> node = node(index);
        E oldElement = node.element;
        node.element = element;
        return oldElement;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        if (index == size) {
            Node<E> oldLast = last;
            last = new Node<>(last, element, null);
            if (oldLast == null) {
                first = last;
            }else {
                oldLast.next = last;
            }
        }else {
            //获取当前节点
            Node<E> next = node(index);
            //获取前一个节点
            Node<E> prev = next.prev;
            Node<E> node = new Node<> (prev,element,next);
            next.prev = node;
            if (prev == null) {//index == 0
                first = node;
            }else {
                prev.next = node;
            }
        }
        size ++;
    }

    /**
     * 删除index位置的节点
     * @param index
     * @return
     */
    public E remove(int index) {
        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        if (prev == null) {
            first = next;
        }else {
            prev.next = next;
        }
        if (next == null) {
            last = prev;
        }else {
            next.prev = prev;
        }
        size--;
        return node.element;
    }

    /**
     * 查看某个节点元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) return i;
                node = node.next;
            }
        }else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element.equals(element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    
    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(node);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
}

根据上面双链表的调用验证结果如下

size=4, [null_11_66, 11_66_33, 66_33_44, 33_44_null]

双向循环链表(java)

链表的设计


代码实现 
package com.njf;

public class DoublyCycleLinkedList<E> {
    /**
     * 链表大小
     */
    private int size;
    /**
     * 指向头结点的引用
     */
    private Node<E> first;
    /**
     * 指向尾结点的引用
     */
    private Node<E> last;
    /**
     * 指向当前节点的引用
     */
    private Node<E> current;
    
    private static final int ELEMENT_NOT_FOUND = -1;
    
    private static class Node<E> {//创建节点
        //数据域
        E element;
        //指向前结点的引用
        Node<E> prev;
        //指向后继结点的引用
        Node<E> next;
        public Node(Node<E> prev,E element, Node<E> next) {//构造函数
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
        
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            if (prev != null) {
                sb.append(prev.element);
            } else {
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if (next != null) {
                sb.append(next.element);
            } else {
                sb.append("null");
            }
            return sb.toString();
        }
    }
    
    /**
     *  获取index位置对应的节点对象
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        if (index < (size>>1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
    
    /**
     * 指向第一个节点
     */
    public void reset() {
        current = first;
    }
    
    /**
     * 返回当前节点指向的下一个节点的元素
     */
    public E next() {
        if (current == null) return null;
        current = current.next;
        return current.element;
    }
    
    /**
     * 清除所有链表数据
     */
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    /**
     * 链表大小
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 链表是否为空
     * @return
     */
    public boolean isEmpty() {
         return size == 0;
    }

    /**
     * 是否包含某个数据元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 添加节点到尾部
     * @param element
     */
    public void add(E element) {
        add(size, element);
    }

    /**
     * 获取index位置的节点中的数据
     * @param index
     * @return
     */
    public E get(int index) {
        return node(index).element;
    }

    /**
     * 设置index位置节点中的数据
     * @param index
     * @param element
     * @return 原来的节点中的数据
     */
    public E set(int index, E element) {
        //获取当前节点
        Node<E> node = node(index);
        E oldElement = node.element;
        node.element = element;
        return oldElement;
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        if (index == size) {
            Node<E> oldLast = last;
            last = new Node<>(last, element, first);
            if (oldLast == null) {
                first = last;
                first.prev = last;
                last.next = first;
            }else {
                oldLast.next = last;
                first.prev = last;
            }
        }else {
            //获取当前节点
            Node<E> next = node(index);
            //获取前一个节点
            Node<E> prev = next.prev;
            Node<E> node = new Node<> (prev,element,next);
            next.prev = node;
            prev.next = node;
            if (next == first) {//index == 0
                first = node;
            }
        }
        size ++;
    }
    
    public E remove() {
        if (current == null) return null;
        Node<E> next = current.next;
        E element = remove(current);
        if (size == 0) {
            current = null;
        }else {
            current = next;
        }
        return element;
    }

    /**
     * 删除index位置的节点
     * @param index
     * @return
     */
    public E remove(int index) {
        return remove(node(index));
    }
    
    private E remove(Node<E> node) {
        if (size == 1) {
            first = null;
            last = null;
        }else {
            Node<E> prev = node.prev;
            Node<E> next = node.next;
            prev.next = next;
            next.prev = prev;
            if (node == first) {
                first = next;
            }
            if (node == last) {
                last = prev;
            }
        }
        size--;
        return node.element;
    }

    /**
     * 查看某个节点元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) return i;
                node = node.next;
            }
        }else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element.equals(element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }
    
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    
    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(node);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }
}

根据上面双链表的调用验证结果如下

size=4, [44_11_66, 11_66_33, 66_33_44, 33_44_11]

利用双向循环链表解决约瑟夫问题（Josephus Problem）

如下：


从第一个元素开始，每次第3个元素杀掉，直到全部杀死为止
用双向循环链表主要实现三个方法
1. 让 current 指向头结点 first 
public void reset() {
        current = first;
 }

2. 让 current 往后走一步，也就是 current = current.next

 public E next() {
        if (current == null) return null;
        current = current.next;
        return current.element;
 }

3. 删除 current 指向的节点，删除成功后让 current 指向下一个节点

public E remove() {
       if (current == null) return null;
       Node<E> next = current.next;
       E element = remove(current);
       if (size == 0) {
           current = null;
       }else {
           current = next;;
       }
       return element;
   }

下面是调用关系

package com.njf;

public class Main 
    static void josephus() {
        DoublyCycleLinkedList<Integer> list = new DoublyCycleLinkedList<>();
        for (int i = 1; i <= 8; i++) {
            list.add(i);
        }
        list.reset();
        while (!list.isEmpty()) {
            list.next();
            list.next();
            System.out.println(list.remove());
        }
    }
    
    public static void main(String[] args) {
        josephus();
    }

每次删除的元素如下：

3
6
1
5
2
8
4
7

相关文章

  • 数据结构 | 其二 链表

    冰河winner - 数据结构之链表 2.1 单向链表 数据结构(一) 单链表的实现-JAVA 2.2 双端链表 ...

  • 集合-LinkedList解析

    一、概要 Java中底层数据结构是链表、双端链表，Android中数据结构是双向循环链表 非线程安全数据结构,允许...

  • 链表

    单链表 C实现 Java实现 双链表 C实现 Java实现

  • 数据结构笔记

    数据结构课程概览 ================== 1.顺序表 2.链表：单链表，单向循环链表，双链表...

  • 常见数据结构和算法

    常见数据结构 线性数据结构（按顺序具有数据元素的数据结构）：数组，堆栈，链表（单链表 双链表），队列非线性数据结...

  • 数据结构-双链表(java)

    简介:双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱 链表的设计 代码实现 根据上面双链表的调用...

  • Java数据结构算法（二）栈和队列

    本文旨作于收集整理使用！！ 导航 Java数据结构算法（一）链表 Java数据结构算法（三）树 Java数据结构算...

  • 数据结构基础2

    1.单链表的数据结构+案例2.双链表的数据结构+案例3.栈的数据结构(双向链表+数组实现) + 案例4.队列的数据...

  • Java数据结构算法（三）树

    本文旨作于收集整理使用！！ 导航 Java数据结构算法（一）链表 Java数据结构算法（二）栈和队列 Java数据...

  • Java数据结构算法（四）图

    本文旨作于收集整理使用！！ 导航 Java数据结构算法（一）链表 Java数据结构算法（二）栈和队列 Java数据...

网友评论

      本文标题：数据结构-双链表(java)

      本文链接：https://www.haomeiwen.com/subject/ixwunhtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数据结构-双链表(java)|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！