数据结构(二) 线性表链式存储

原理：用一组任意的存储单元存储线性表元素。

原理图：

算法原理：

1、为了表示数据元素a和他直接后继元素的关系a+1的逻辑关系，对数据元素a来说除了存储本身的数据信息外，再开辟一块空间存储直接后继元素位置，存储数据信息的区域称为数据域，存储直接后继元素位置的区域称为指针域，指针域存储的信息称为指针或者链，两部分数据组成的元素称为结点(Node),

2、插入元素即为创建新结点的过程

假设存储数据e的结点为s，将 s 插入大到p —> p-next之间，只需要让 p —> s , s —> p-next做一下指针变化即可

3、删除元素即为重新设置其直接前驱和直接后记元素的指针的过程(原理同上图）

4、查询元素即为从头部或者尾部遍历的过程

总结：

1、相对于顺序存储结构，链表不需要预先分配存储空间，随时分配

2、插入和删除不需要移动元素，效率更快

3、存取需要遍历表效率低于顺序表

实现代码：

接口定义：

 1 package online.jfree.base.container;
 2 
 3 /**
 4  * author : Guo LiXiao
 5  * date : 2017-6-14  11:46
 6  */
 7 
 8 public interface LineList <E>{
 9 
10     /**
11      * lineList 是否为空
12      * @return
13      */
14     boolean isEmpty();
15 
16     /**
17      * 清空 lineList
18      */
19     void clear();
20 
21     /**
22      * 获取指定位置元素
23      * @param index
24      * @return
25      */
26     E get(int index);
27 
28     /**
29      * 获取元素第一次出现的位置
30      * @param e
31      * @return
32      */
33     int indexOf(E e);
34 
35     /**
36      * 判断 lineList是否包含指定元素
37      * @param e
38      * @return
39      */
40     boolean contains(E e);
41 
42     /**
43      * 设置指定位置数据，如数据已存在 则覆盖原数据
44      * @param index
45      * @param e
46      * @return
47      */
48     E set(int index, E e);
49 
50     /**
51      * 移除指定位置元素
52      * @param index
53      * @return
54      */
55     E remove(int index);
56 
57     /**
58      * 在lineList结尾插入元素
59      * @param e
60      * @return
61      */
62     E add(E e);
63 
64     /**
65      * 在index后面插入元素
66      * @param index
67      * @param e
68      * @return
69      */
70     E add(int index, E e);
71 
72     /**
73      * 返回lineList长度
74      * @return
75      */
76     int size();
77 
78 
79 
80 }

View Code

 1 package online.jfree.base.container.list;
 2 
 3 import online.jfree.base.container.LineList;
 4 
 5 /**
 6  * author : Guo LiXiao
 7  * date : 2017-6-19  10:16
 8  */
 9 
10 public abstract class AbstractLineList<E> implements LineList<E> {
11 
12     protected int size;
13 
14     protected abstract void init();
15 
16     @Override
17     public boolean isEmpty() {
18         return this.size == 0;
19     }
20 
21     @Override
22     public void clear() {
23         init();
24     }
25 
26     @Override
27     public int size() {
28         return this.size;
29     }
30 
31     @Override
32     public boolean contains(E e) {
33         return indexOf(e) > 0;
34     }
35 }

View Code

单链表实现(单链表结点只有一个指针域，存储直接前驱或者直接后继结点)：

  1 package online.jfree.base.container.list;
  2 
  3 import online.jfree.base.container.LineList;
  4 
  5 /**
  6  * 线性表的链式存储结构
  7  * author : Guo LiXiao
  8  * date : 2017-6-7  14:52
  9  */
 10 
 11 public class LinkedLineList<E> extends AbstractLineList<E> implements LineList<E> {
 12 
 13     transient Node<E> first;
 14 
 15     public LinkedLineList() {
 16     }
 17 
 18     @Override
 19     protected void init() {
 20         this.size = 0;
 21         first = null;
 22     }
 23 
 24     /**
 25      * 根据索引获取元素
 26      * @param index
 27      * @return
 28      */
 29     protected Node<E> node(int index) {
 30         Node<E> x = first;
 31         for (int i = 0; i < index; i++)
 32             x = x.next;
 33         return x;
 34     }
 35 
 36     /**
 37      * 校验列表索引越界
 38      *
 39      * @param index
 40      */
 41     private void checkCapacity(int index) {
 42         if (index >= size || index < 0)
 43             throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString());
 44     }
 45 
 46 
 47     @Override
 48     public E get(int index) {
 49         checkCapacity(index);
 50         return node(index).item;
 51     }
 52 
 53     @Override
 54     public int indexOf(E e) {
 55         int index = 0;
 56         for (Node<E> x = first; x != null; x = x.next) {
 57             if (e == null && x.item == null || e.equals(x.item))
 58                 return index;
 59             index++;
 60         }
 61         return -1;
 62     }
 63 
 64     @Override
 65     public E set(int index, E e) {
 66         checkCapacity(index);
 67         Node<E> node = node(index);
 68         E old = node.item;
 69         node.item = e;
 70         return old;
 71     }
 72 
 73     @Override
 74     public E remove(int index) {
 75         checkCapacity(index);
 76         if (index == 0) {
 77             Node<E> node = first;
 78             Node<E> next = node.next;
 79             first = next;
 80             size --;
 81             return first.item;
 82         } else {
 83             Node<E> pre = node(index - 1);
 84             Node<E> node = pre.next;
 85             Node<E> next = node.next;
 86             pre.next = next;
 87             size --;
 88             return node.item;
 89         }
 90     }
 91 
 92     @Override
 93     public E add(E e) {
 94         if (size == 0) {
 95             first = new Node<>(e, null);
 96             size ++;
 97             return first.item;
 98         }
 99         return add(size - 1, e);
100     }
101 
102     @Override
103     public E add(int index, E e) {
104         checkCapacity(index);
105         Node<E> node = node(index);
106         Node<E> next = node.next;
107         node.next = new Node<>(e, next);
108         size ++;
109         return node.next.item;
110     }
111 
112     private static final class Node<E> {
113         E item;
114         Node<E> next;
115 
116         public Node(E item, Node<E> next) {
117             this.item = item;
118             this.next = next;
119         }
120     }
121 }

View Code

双向链表实现(双向链表结点有两个指针域，存储直接前驱和直接后继结点)：

  1 package online.jfree.base.container.list;
  2 
  3 import online.jfree.base.container.LineList;
  4 
  5 /**
  6  * 线性表 双向链表
  7  * author : Guo LiXiao
  8  * date : 2017-6-19  9:59
  9  */
 10 
 11 public class DualLinkedLineList<E> extends AbstractLineList<E> implements LineList<E> {
 12 
 13     private transient Node<E> first;
 14     private transient Node<E> last;
 15 
 16     /**
 17      * 根据索引获取元素
 18      *
 19      * @param index
 20      * @return
 21      */
 22     protected Node<E> node(int index) {
 23         if (index < (size >> 1)) {
 24             Node<E> x = first;
 25             for (int i = 0; i < index; i++)
 26                 x = x.next;
 27             return x;
 28         } else {
 29             Node<E> x = last;
 30             for (int i = size - 1; i > index; i--)
 31                 x = x.prev;
 32             return x;
 33         }
 34     }
 35 
 36     /**
 37      * 校验列表索引越界
 38      *
 39      * @param index
 40      */
 41     private void checkCapacity(int index) {
 42         if (index >= size || index < 0)
 43             throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString());
 44     }
 45 
 46 
 47     @Override
 48     protected void init() {
 49         this.size = 0;
 50         first = null;
 51         last = null;
 52     }
 53 
 54     @Override
 55     public E get(int index) {
 56         checkCapacity(index);
 57         return node(index).item;
 58     }
 59 
 60     @Override
 61     public int indexOf(E e) {
 62         int index = 0;
 63         for (Node<E> x = first; x != null; x = x.next) {
 64             if (e == null && x.item == null || e.equals(x.item))
 65                 return index;
 66             index++;
 67         }
 68         return -1;
 69     }
 70 
 71     @Override
 72     public E set(int index, E e) {
 73         checkCapacity(index);
 74         Node<E> node = node(index);
 75         E old = node.item;
 76         node.item = e;
 77         return old;
 78     }
 79 
 80     @Override
 81     public E remove(int index) {
 82         checkCapacity(index);
 83         Node<E> node = node(index);
 84         final E e = node.item;
 85         final Node<E> next = node.next;
 86         final Node<E> prev = node.prev;
 87         if (prev == null) {
 88             first = next;
 89             first.prev = null;
 90         } if (next == null){
 91             last = prev;
 92             last.next = null;
 93         } else {
 94             prev.next = next;
 95             next.prev = prev;
 96         }
 97         size--;
 98         return e;
 99     }
100 
101     @Override
102     public E add(E e) {
103         if (first == null) {
104             first = new Node<>(null, e, null);
105             last = first;
106             size ++;
107             return first.item;
108         }
109         return add(size - 1, e);
110     }
111 
112     @Override
113     public E add(int index, E e) {
114         checkCapacity(index);
115         Node<E> node = node(index);
116         Node<E> next = node.next;
117         node.next = new Node<>(node, e, next);
118         if (next == null) last = node.next;
119         size ++;
120         return node.next.item;
121     }
122 
123     private static final class Node<E> {
124         E item;
125         Node<E> prev;
126         Node<E> next;
127 
128         public Node(Node<E> prev, E item, Node<E> next) {
129             this.item = item;
130             this.prev = prev;
131             this.next = next;
132         }
133     }
134 
135 }

View Code