首页 > 代码库 > 线性表-双向链表（LinkedList）

线性表-双向链表（LinkedList）

2024-08-05 16:09:51   220人阅读

双向链表：如图1-3 所示，会把当前header拆分开，重新插入一个Entry<E>。

LinkedList源码  

0.首先这个类中的两个变量

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

下面的这个size就不用说了，是大小，现在先着重看看 Entry<E> header，

Entry是一个内部类。

Java代码  收藏代码
  1. private static class Entry<E> {  
  2.    E element;  
  3.    Entry<E> next;  
  4.    Entry<E> previous;  
  5.   
  6.    Entry(E element, Entry<E> next, Entry<E> previous) {  
  7.                    this.element = element;  
  8.                    this.next = next;  
  9.                    this.previous = previous;  
  10.                }  
  11.    }      

    

 

    就是一个链表，有父节点和子节点，父子节点都是一个对象的引用。

    还有就是这个类是LinkedList的内部类，所以变量自然能再外部直接调用了。

1.构造函数


    这个对象在声明的时候已经new了一个对象，所以这里可以直接使用里面的方法
    节点的子节点和父节点都自己。

Java代码  收藏代码
  1. //无参构造     
  2.  public LinkedList() {  
  3.         header.next = header.previous = header;  
  4.     }  

   

    这里是无参构造后header的示意图，父子节点都指向自己。只是最初的header对象。

    这里所指向的“一个对象”在初始化中为null 。并且没有改变过。

 

Java代码  收藏代码
  1. //有参构造   
  2.   public LinkedList(Collection<? extends E> c) {  
  3.             //这一句可不能忘，对头节点的初始化很重要。  
  4.             this();  
  5.             addAll(c);  
  6.     }  

   在有了添加元素的操作后，entry的指针会指向不同地方。

2.add方法

    这个方法主要是讲原来

    返回是否成功

Java代码  收藏代码
  1. public boolean add(E e) {  
  2.         addBefore(e, header);  
  3.             return true;  
  4. }  
  5.   
  6.  private Entry<E> addBefore(E e, Entry<E> entry) {  
  7.          //新建一个节点，子节点是头结点，这样看来它是环形链表。  
  8.          //它的父节点在第一次添加的时候是头结点，以后会得到最后一次添加的节点，并且在下面会断开后重连。  
  9.             Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  
  10.             //新节点的上一个节点的子节点设置为新的节点  
  11.             newEntry.previous.next = newEntry;  
  12.             //新节点的下一个节点的父节点设置为新的节点  
  13.             newEntry.next.previous = newEntry;  
  14.             //大小++  
  15.             size++;  
  16.             //这个不知道  
  17.             modCount++;  
  18.             //返回新的节点。  
  19.             return newEntry;  
  20. }  

 

Java代码  收藏代码
  1. //在第几个位置添加  
  2.      public void add(int index, E element) {  
  3.          //如果在最后的位置添加，直接和上面的添加一样，如果不是，则  
  4.         addBefore(element, (index==size ? header : entry(index)));  
  5.     }  
  6.      
  7.      private Entry<E> entry(int index) {  
  8.         if (index < 0 || index >= size)  
  9.             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
  10.         //取得头结点  
  11.         Entry<E> e = header;  
  12.        <span style="color: #ff0000;"> //循环节点，从头节点开始循环，这个处理很聪明，先计算index的大小，小于一半的话正向遍历，大于一半的话反向遍历。</span>  
  13.   
  14.   
  15.   
  16.   
  17.   
  18.   
  19.         if (index < (size >> 1)) {  
  20.             for (int i = 0; i <= index; i++)  
  21.                 e = e.next;  
  22.         } else {  
  23.             for (int i = size; i > index; i--)  
  24.                 e = e.previous;  
  25.         }  
  26.         //最后返回节点。  
  27.         return e;  
  28.     }  

 

Java代码  收藏代码
  1. //添加到第一个位置  
  2.   public void addFirst(E e) {  
  3.        //只是在header的下一个开始添加，不多看了。  
  4.     addBefore(e, header.next);  
  5.     }  

 

Java代码  收藏代码
  1. public void addLast(E e) {  
  2.    //这个和add方法一样，所以普通的添加方法也是添加到最后的位置。  
  3.    addBefore(e, header);  
  4.   }  

 


                                   图1-3

 

    这个是完整的情况，添加，删除都会断开相应的next和previous。同时注意header内部的element不会存储元素。他所指向的对象是null ，在前面也说过。

  3.remove

  主要是讲要删除元素的Entry调整父子节点就可实现删除。

Java代码  收藏代码
  1. public E remove() {  
  2.         return removeFirst();  
  3.     }  
  4.      
  5.      public E removeFirst() {  
  6.             return remove(header.next);  
  7.     }  
  8.      
  9.      private E remove(Entry<E> e) {  
  10.      //不能删除头节点  
  11.                 if (e == header)  
  12.                     throw new NoSuchElementException();  
  13.                 //这个是用来返回的  
  14.               E result = e.element;  
  15.               //父节点的子节点指向e的子节点。  
  16.                 e.previous.next = e.next;  
  17.                 //子节点的父节点指向e的父节点  
  18.                 e.next.previous = e.previous;  
  19.                 //将e设为空。  
  20.                     e.next = e.previous = null;  
  21.                     e.element = null;  
  22.               //大小--  
  23.                 size--;  
  24.                 modCount++;  
  25.              return result;  
  26.     }  

  删除元素。这里面的匹配和indexof方法很像。在indexof里面讲。

Java代码  收藏代码
  1. public boolean remove(Object o) {  
  2.        if (o==null) {  
  3.            for (Entry<E> e = header.next; e != header; e = e.next) {  
  4.                if (e.element==null) {  
  5.                    remove(e);  
  6.                    return true;  
  7.                }  
  8.            }  
  9.        } else {  
  10.            for (Entry<E> e = header.next; e != header; e = e.next) {  
  11.                if (o.equals(e.element)) {  
  12.                    remove(e);  
  13.                    return true;  
  14.                }  
  15.            }  
  16.        }  
  17.        return false;  
  18.    }  

 

  4.indexOf

 

Java代码  收藏代码
  1. //还<span style="color: #ff0000;">是对equals比较</span>  
  2.   
  3.   
  4.   
  5. ，都是正向循环。没什么新意，循环到头指针后结束。  
  6.      public int indexOf(Object o) {  
  7.         int index = 0;  
  8.         if (o==null) {  
  9.             for (Entry e = header.next; e != header; e = e.next) {  
  10.                 if (e.element==null)  
  11.                     return index;  
  12.                 index++;  
  13.             }  
  14.         } else {  
  15.             for (Entry e = header.next; e != header; e = e.next) {  
  16.                 if (o.equals(e.element))  
  17.                     return index;  
  18.                 index++;  
  19.             }  
  20.         }  
  21.         return -1;  
  22.     }  

    还有一些找第几个元素，返回元素数量，找到头元素，找都最后元素。

 

此文转载至：http://wdhdmx.iteye.com/blog/1161972

线性表-双向链表（LinkedList）


联系
我们