LinkedList

先来一个LinkedList压压惊

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    transient int size = 0;
    
    transient Node<E> first;
    
    transient Node<E> last;
    
    public LinkedList() {
    }

    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
    //LinkedList主要用一下结构来保存数据
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

感觉这个数据结构有点简单  不做详细分析了 没意思
简单的其他几个问题总结:
1、为什么不能使用for循环去遍历?
for (int i = 0; i < 100; i++){
        System.out.println(linkedList.get(i));
    }
答:因为在使用for循环拿到所以之后,LinkedList还得再去进行依次遍历这个索引就是下一次需要遍历的次数,根据这个次数顺着node结点链去找对应的节点值
    所以for循环遍历相当与有两次遍历 而直接使用迭代器,那么就相当与直接顺着node结点去取值,只遍历一次。
    
2、简单解释一下位运算
  7<<3   结果为567转化成2进制 0000 0000 0000 0000 0000 0000 0000 0111
  然后左移30000 0000 0000 0000 0000 0000 0011 1000
  得到的正好就是56  也就是7*2*2*256
  
  8>>4   结果为08转化成2进制 0000 0000 0000 0000 0000 0000 0000 1000
  然后右移40000 0000 0000 0000 0000 0000 0000 0000
  得到的正好就是0   也就是8/2/2/2/2    当这个结果>=1的时候,取计算结果  否则取0
  
  负数的位运算
  -7<<3   结果为-56-7转化为2进制 1000 0000 0000 0000 0000 0000 0000 0111
  然后写出补码    1111 1111 1111 1111 1111 1111 1111 1001  首位的符号位不变,其余位置取反,然后再+1
  然后左移31111 1111 1111 1111 1111 1111 1100 0111  左移,低位补0  然后再-1
  根据补码写出源码 1000 0000 0000 0000 0000 0000 0011 1000  首位的符号位不变,其余位置取反
  得到的刚好是-56  也就是-7*2*2*2-56
  
  -8>>4  结果为-1-8转化为2进制 1000 0000 0000 0000 0000 0000 0000 1000
  然后写出补码    1111 1111 1111 1111 1111 1111 1111 1000  首位的符号位不变,其余位置取反,然后再+1
  然后右移四位    1111 1111 1111 1111 1111 1111 1111 1110  右移 高位补1 然后再-1
  根据补码写出源码 1000 0000 0000 0000 0000 0000 0000 0001  首位不变,其他取反
  得到的刚好是 -1  也就是-8/2/2/2/2    当这个结果<=-1的时候,取计算结果  否则取-1
  
  以上两个都是带符号的位运算  无符号的位运算计算方式如下:
  不带符号的主要是负数会有影响  左移不影响符号位
  -7<<<3  程序编译错误! 7<<<  程序编译错误! 8>>>4 == 8>>4
  
  -8>>>4-8转化为2进制 1000 0000 0000 0000 0000 0000 0000 1000
  然后写出补码    1111 1111 1111 1111 1111 1111 1111 1000  首位的符号位不变,其余位置取反,然后再+1
  然后右移四位    0000 1111 1111 1111 1111 1111 1111 1111  右移 得到的是正数  不需要-1
  得到的刚好是 ......
  由于这个数值太大  我们取右移310000 0000 0000 0000 0000 0000 0000 0001 刚好是1
  
  3、为什么jdk1.6之后 LinkedList不再是循环链表?
  循环链表从任意一个结点触发都可以访问到其他链表?  貌似不循环的也可以访问到
  
  缺点:循环链表需要维护首尾的关系,恰恰首尾是操作最频繁的,所以这样他的效率会极大降低。
匿名

发表评论

匿名网友