[图解数据结构之Java实现](2) --- 线性表之链表实现

本文行文思路结构

一. 线性表
二. Java中的指针
三. 表的简单链表实现
四. 表的各种基本操作 --- 增删改查
    1. 图解分析
    2. 代码实现
五. 完整代码Demo
六. 总结

一. 线性表

部分定义和解释见下面链接:
http://blog.csdn.net/menglanyingfei/article/details/71519202

二. Java中的"指针"

首先, 学过C++的人肯定知道, Java比C++更安全. 当然, 在这里, 你只需要知道, Java中的引用(Reference)是一种受限制的(C++中)指针!

三. 表的简单链表实现

如何懂C/C++中链表是如何实现? 对于Java实现则完全是大同小异!
C语言链表实现的参考:
http://blog.csdn.net/menglanyingfei/article/details/52710574

我们知道Java中的链表LinkedList是用双向链表来实现的.
所以, 关于自己实现的链表类MyLinkedList, 在类的设计上:

MyLinkedList类本身, 它包含到两端的链, 表的大小以及一些方法;
Node类, 它可能是一个私有的嵌套类. 一个节点包含数据以及前一个节点的链和到下一个节点的链, 还有一些适当的构造方法;
LinkedListedIterator类, 该类抽象了位置的概念, 是一个私有类, 并实现接口Iterator. 它提供了方法next(), hasNext(), remove()的实现. (如果初学Java, 关于集合框架的迭代器部分可跳过!)

MyLinkedList.png

四. 表的各种基本操作 --- 增删改查

1. 图解分析

具有头节点和尾节点的空双链表.png

addBefore方法.png

remove方法.png

2. 代码实现

增.png

删.png

改.png

查.png

五. 完整代码Demo

部分测试用例.png

MyLinkedList.java

package org.lxy.ds;

import java.util.ConcurrentModificationException;
import java.util.Iterator;

/**
 * 
 * @author lxy
 *
 * @param <E>
 */
public class MyLinkedList<E> implements Iterable<E> {
    private int theSize; // 容器内元素的个数
    private int modCount = 0; // Modified Count代表自从构造以来对链表所做改变的次数
    private Node<E> beginMarker;
    private Node<E> endMarker;

    // 静态内部类Node实现节点之间的连接
    private static class Node<E> {
        public E data;
        public Node<E> prev;
        public Node<E> next;

        public Node(E d, Node<E> p, Node<E> n) {
            data = d;
            prev = p;
            next = n;
        }
    }
    
    // 无参的构造方法, 构造一个MyLinkedList类的对象之前, 清空里面的元素
    public MyLinkedList() {
        clear();
    }

    public void clear() {
        beginMarker = new Node<E>(null, null, null);
        endMarker = new Node<E>(null, beginMarker, null);
        beginMarker.next = endMarker;

        theSize = 0;
        modCount++;
    }
    
    // 下面的方法, 即对容器(MyLinkedList对象)的操作, 方法名大多见名知义
    public int size() {
        return theSize;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean add(E x) {
        add(size(), x);
        return true;
    }

    public void add(int idx, E x) {
        addBefore(getNode(idx), x);
    }

    public E get(int idx) {
        return getNode(idx).data;
    }

    public E set(int idx, E newVal) {
        Node<E> p = getNode(idx);
        E oldVal = p.data;
        p.data = newVal;
        return oldVal;
    }

    public E remove(int idx) {
        return remove(getNode(idx));
    }

    private void addBefore(Node<E> p, E x) {
        Node<E> newNode = new Node<E>(x, p.prev, p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        theSize++;
        modCount++;
    }

    private E remove(Node<E> p) {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;
        
        return p.data;
    }

    private Node<E> getNode(int idx) {
        Node<E> p;
        
        if (idx < 0 || idx > size()) {
            throw new IndexOutOfBoundsException();
        }
        if (idx < size() / 2) {
            p = beginMarker.next;
            for (int i = 0; i < idx; i++) {
                p = p.next;
            }
        } else {
            p = endMarker;
            for (int i = size(); i > idx; i--) {
                p = p.prev;
            }
        }
        
        return p;
    }

    @Override
    public Iterator<E> iterator() {

        return new LinkedListItetator();
    }

    // MyLinkedList类中的内部Iterator类
    private class LinkedListItetator implements Iterator<E> {
        private Node<E> current = beginMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;
        
        @Override
        public boolean hasNext() {
            return current != endMarker;
        }
        
        @Override
        public E next() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!okToRemove) {
                throw new IllegalStateException();
            }
            
            E nextItem = current.data;
            current = current.next;
            okToRemove = true;
            
            return nextItem;
        }
        
        @Override
        public void remove() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (!okToRemove) {
                throw new IllegalStateException();
            }
            MyLinkedList.this.remove(current.prev);
            okToRemove = false;
            expectedModCount++;
        }
    }

}

MyLinkedListTest.java

package org.lxy.ds;
/**
 * @author menglanyingfei
 * @date 2017-5-14
 */
public class MyLinkedListTest {
    public static void main(String[] args) {
        MyLinkedList<Integer> myLinkedList = new MyLinkedList<>();
        myLinkedList.add(1);
        myLinkedList.add(2);
        myLinkedList.add(3);
        myLinkedList.add(4);
        myLinkedList.add(5);
        
        System.out.println(myLinkedList.size()); // 5
        
        System.out.println(myLinkedList.get(0)); // 1
        System.out.println(myLinkedList.get(1)); // 2
        
        System.out.println(myLinkedList.set(0, 15)); // 1, set方法返回之前被修改的旧值
        System.out.println(myLinkedList.get(0)); // 15
        
        System.out.println(myLinkedList.remove(0)); // 15
        System.out.println(myLinkedList.get(0)); // 2
        
    }
}

个人博客:(一个一直在坚持认真学习Java的大三学生)
博客地址

六. 总结

Java中实现链表, 非常类似C++中, 只要知道其中的对应关系和指针如何指向, 同时注意容器中元素的界限问题, 明白这个实现原理, 应该不难的!

参考

http://www.importnew.com/18968.html
http://www.cnblogs.com/ITtangtang/p/3948610.html
数据结构与算法分析-Java语言描述

一点感悟与您分享

最近一段时间, 突然发现了: 在文学上, 这句话很经典.

悲剧就是把美好的东西毁灭给人看. -- 鲁迅

生活中, 有各种开心与悲伤, 其实, 在人内心深处是有一种对美好事物的向往, 由于它的存在, 才产生了各种目标与信念. 但人真是一种奇怪的生物, 往往对自己现在或者所拥有的事物不太注意和爱惜, 只在失去之后, 才知道它的珍贵!
这或许, 谈不上一种毁灭, 但不懂得珍惜, 也是让现在的自己所拥有的美好事物一点一点地失去......
个人对生活和人生的一点思考, 也希望看到这段文字的您有所感触和思考!