自己写LinkedList GoLinkedList

www.allocmem.com · · 3583 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

##前言:   java GoLinkedList的简易实现,代码中注释比较详尽,通俗易懂,注意事项亦在注解中标明。 ###正文:

  1. GoLinkedList.java

    	package com.anteoy.dataStructuresAndAlgorithm.javav2.my;
    
    
    	import java.util.Iterator;
    
    
    	/**
    	 * Created by zhoudazhuang on 17-3-1.
    	 * Description: 简易Linkedlist实现
    	 */
    	public class GoLinkedList<T> implements Iterable<T>{
    
    
    	    //当前容量 size
    	    private int currentSize;
    
    
    	    //附加的数据域 用来帮助迭代气检测集合中的变化 代表自从构造依赖对链表所做改变的次数 当和迭代器内储存的modCount不一致则抛出异常
    	    private int modCount = 0;
    
    
    	    //头节点 注意没有值和前趋节点 只有后继节点(指向下一个节点的链)
    	    private Node<T> beginMarker;
    	    //尾节点 和头节点相反
    	    private Node<T> endMarker;
    
    
    	    /**
    	     * 私有静态嵌套类
    	     * 在一个类中,数据成员通常都是私有的
    	     * prev,next都是Node的实例
    	     * @param <AnyType>
    	     */
    	    private static class Node<AnyType> {
    	        //信使携带数据
    	        public AnyType data;
    	        //到前一个节点的链 主要注意这里的链其实也是一个节点Node
    	        public Node<AnyType> prev;
    	        //到下一个节点的链 主要注意这里的链其实也是一个节点Node
    	        public Node<AnyType> next;
    
    
    	        //构造函数
    	        public Node( AnyType d, Node<AnyType> p, Node<AnyType> n ) {
    	            data = d; prev = p; next = n;
    	        }
    	    }
    
    
    	    public GoLinkedList()
    	    {
    	        clear();
    	    }
    
    
    	    /**
    	     * 创建并连接头尾节点,然后设置大小为0
    	     */
    	    private void clear() {
    	        beginMarker = new Node<T>(null,null,null);
    	        endMarker = new Node<T>(null,beginMarker,null);
    	        beginMarker.next = endMarker;
    
    
    	        currentSize = 0;
    	        modCount++;
    	    }
    
    
    	    public int size(){
    	        return currentSize;
    	    }
    
    
    	    /**
    	     * 判断是否为空
    	     * @return
    	     */
    	    public boolean isEmpty(){
    	        return size() == 0;
    	    }
    
    
    	    public boolean add(T x){
    	        add(size(),x);
    	        return true;
    	    }
    
    
    	    public boolean add(int idx, T x){
    	       return addBefore( getNode(idx), x );
    	    }
    
    
    	    public T get(int idx){
    	        return getNode(idx).data;
    	    }
    
    
    	    public T set (int idx, T newVal){
    	        Node<T> p = getNode(idx);
    	        T oldVal = p.data;
    	        p.data = newVal;
    	        return oldVal;
    	    }
    
    
    	    public T remove(int idx){
    	        return remove(getNode(idx));
    	    }
    
    
    	    /**
    	     * 通过获取一个新节点,然后按所只是的顺序改变指针
    	     * 完成一个双向链表中的插入操作
    	     * @param p
    	     * @param x
    	     */
    	    public boolean addBefore(Node<T> p, T x){
    	        //使用信使储存新node 前一个链为p.prev 后一个链为p 前趋后继 表示插入在p和p之前一个节点之间
    	        Node<T> newNode = new Node<>(x, p.prev, p);
    	        //newNode的前节点的后一个链赋为本身
    	        newNode.prev.next = newNode;
    	        //改变p的前节点为newNode
    	        p.prev = newNode;
    	        //容量+1
    	        currentSize++;
    	        //操作次数加1
    	        modCount++;
    	        return true;
    	    }
    
    
    	    /**
    	     * 删除p节点
    	     * @param p
    	     * @return 删除的节点
    	     */
    	    private T remove(Node<T> p){
    	        //节点p的后继节点的前趋链被赋予当前p的前趋节点
    	        p.next.prev = p.prev;
    	        //类似上面理解
    	        p.prev.next = p.next;
    	        //大小减1
    	        currentSize--;
    	        //操作次数加1
    	        modCount++;
    	        return p.data;
    	    }
    
    
    	    /**
    	     * 这里进行折半分流遍历
    	     * @param idx
    	     * @return
    	     */
    	    private Node<T> getNode(int idx)
    	    {
    	        Node<T> p;
    
    
    	        //不符合规则 直接抛异常
    	        if(idx<0 || idx>size())
    	            throw new IndexOutOfBoundsException();
    	        //如果索引表示该表前半部分的一个节点
    	        if(idx<size()/2) {//地址空间不连续 不能想ArrayList那样获取 内部实现是双向链表 而不是数组 所以根据指向节点遍历获取值
    	            //比如这里获取的是索引idx的前一个节点的直接后继
    	            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;
    	    }
    
    
    	    public Iterator<T> iterator(){
    	        return new LinkedListIterator();
    	    }
    
    
    	    /**
    	     * 抽象了位置概念
    	     */
    	    private class LinkedListIterator implements java.util.Iterator<T> {
    	        //表示包含由next所返回的项的节点
    	        private Node<T> current = beginMarker.next;
    	        //主要为了保证操作是安全的
    	        private int expectedModCount = modCount;
    	        //保留一个当前位置 检测能否remove
    	        private boolean okToRemove = false;
    
    
    	        //简单实现 不检查链表的修改
    	        public boolean hasNext() {
    	            return current != endMarker;
    	        }
    
    
    	        public T next() {
    	            if (modCount != expectedModCount)
    	                throw new java.util.ConcurrentModificationException();
    	            if (!hasNext())
    	                throw new java.util.NoSuchElementException();
    
    
    	            T nextItem = current.data;
    	            current = current.next;
    	            okToRemove = true;
    	            return nextItem;
    	        }
    
    
    	        public void remove()
    	        {
    	            if(modCount!=expectedModCount)
    	                throw new java.util.ConcurrentModificationException();
    	            if(!okToRemove)
    	                throw new IllegalStateException();
    	            GoLinkedList.this.remove(current.prev);
    	            expectedModCount++;
    	            okToRemove = false;
    	        }
    	    }
    
    
    	}
    
    
    
  2. GoLinkedListTest.java

    	package com.anteoy.dataStructuresAndAlgorithm.javav2.my;
    
    
    	/**
    	 * Created by zhoudazhuang on 17-3-1.
    	 * Description: GoLinkedList测试
    	 */
    	public class GoLinkedListTest {
    
    
    	    public static void main(String[] args) {
    	        GoLinkedList<Integer> goLinkedList = new GoLinkedList<>();
    	        goLinkedList.add(1);
    	        goLinkedList.add(2);
    	        goLinkedList.add(3);
    	        goLinkedList.add(2,4);
    	        for (Integer go:goLinkedList){
    	            System.out.println(go);
    	        }
    	        System.out.printf(String.valueOf(goLinkedList.get(1)));
    	    }
    	}
    

    输出结果:

    	1
    	2
    	4
    	3
    	2
    	Process finished with exit code 0
    

    ###后记:

  3. 参考文献:数据结构与算法分析

本文来自:www.allocmem.com

感谢作者:www.allocmem.com

查看原文:自己写LinkedList GoLinkedList

3583 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传