一、线性表

  线性表分为顺序存储结构和链式存储结构,上一篇讲解了使用顺序存储结构实现线性表,下面讲解使用链式存储结构实现线性表。

二、什么是链式存储结构

  链式存储结构,又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素,它的存储单元可以是连续的,也可以是不连续的。在表示数据元素之间的逻辑关系时,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置),这两部分信息组成数据元素的存储映像,称为结点(node)。它包括两个域;存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。

三、单链表

  单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

1、定义结点

  单链表的结点由元素(数据元素的映象) + 指针(指示后继元素存储位置)组成,由于存储的数据类型不确定,我们使用泛型来表示未确定的数据类型。

 1/**
 2 * 单链表的结点
 3 **/
 4public class ListNode<T> {
 5    /**
 6     * 存储数据
 7     */
 8    protected T data;
 9    /**
10     * 存储后继
11     */
12    protected ListNode<T> next;
13
14    /**
15     * 创建结点并初始化值
16     */
17    public ListNode(T data) {
18        this.data = data;
19    }
20}

2、实现单链表

  单链表也实现上一篇定义的 MyList 接口。firstlast 分别存储单链表的开头和结尾,尾结点的后继为 nullsize 表示单链表的长度,即结点的个数。

 1/**
 2 * 单链表
 3 **/
 4public class SingleLinkedList<T> implements MyList<T> {
 5
 6    /**
 7     * 开头(头结点)
 8     */
 9    public ListNode<T> first;
10    /**
11     * 结尾(尾结点)
12     */
13    private ListNode<T> last;
14    /**
15     * 链表的长度,结点的个数
16     */
17    private int size = 0;
18}
1)添加结点

  向单链表中添加结点分两种情况:

  1. 单链表为空:则新加的结点,既为单链表的头结点又为单链表的尾结点。
  2. 单链表不为空:直接将结点追加到单链表的尾结点,并更新单链表尾结点的值。
 1    @Override
 2    public void add(T value) {
 3        // 如果单链表为空,则将结点赋给单链表的头结点和尾结点
 4        if (first == null) {
 5            first = new ListNode<>(value);
 6            last = first;
 7        } else {
 8            // 如果单链表有结点,则直接向后追加并更新尾结点的值
 9            last.next = new ListNode<>(value);
10            last = last.next;
11        }
12	// 更新单链表的长度
13        size++;
14    }
2)插入结点

  向单链表中插入结点分三种情况:

  1. 向头部添加结点:更换单链表的头结点,并将新结点的后继指向单链表的原头结点。
  2. 向尾部添加结点:直接调用 add 方法即可。
  3. 向单链表中添加结点:先遍历链表,找到结点应插入的位置。然后将新结点的后继指向当前结点,将当前结点的原前驱的后继指向新结点即可。
 1    @Override
 2    public void insert(int index, T value) {
 3        // 如果下标等于0,则更换单链表的头结点
 4        if (index == 0) {
 5            ListNode<T> newNode = new ListNode<>(value);
 6            newNode.next = first;
 7            first = newNode;
 8            // 更新单链表的长度
 9            size++;
10        } else if (index == size) {
11            // 如果下标等于size,则是向单链表的末尾添加结点,直接调用 add 方法即可
12            add(value);
13        } else if (index > -1 && index < size) {
14            // 如果下标大于-1且小于元素的个数,则表示向单链表中插入结点
15            ListNode<T> newNode = new ListNode<>(value);
16            // 指针指向的结点的索引
17            int i = 0;
18            // p是遍历链表的指针
19            ListNode<T> p = first;
20            // pre记录p的前驱(前一个元素)
21            ListNode<T> pre = null;
22            while (p != null) {
23                // 找到结点后,将新结点的后继指向p,将p的原前驱的后继指向新结点即可
24                if (i == index) {
25                    pre.next = newNode;
26                    newNode.next = p;
27                    // 更新单链表的长度
28                    size++;
29                    break;
30                }
31                // 更新结点的值,向后遍历
32                pre = p;
33                p = p.next;
34                // 下标自加
35                i++;
36            }
37        }
38    }
3)删除结点

  删除元素的方式分为:根据下标删除元素和根据元素值删除元素。

  根据值删除结点,首先遍历单链表查找第一个和该值相同的结点,然后将其删除。

  1. 结点不存在:直接退出。
  2. 结点为头结点:用该结点的后继覆盖单链表的头结点即可。
  3. 结点为中间结点:将该结点的前驱指向该结点的后继。
  4. 结点为尾结点:用该结点的前驱覆盖单链表的尾结点即可。

  我们在删除结点时,会用到该结点的前驱和后继,而单链表只有后继的指针,所以我们在遍历单链表时,需要将当前结点的前驱保存起来。

 1    @Override
 2    public void delete(T value) {
 3        // p是遍历链表的指针
 4        ListNode<T> p = first;
 5        // pre记录p的前驱(前一个元素)
 6        ListNode<T> pre = null;
 7        // 遍历链表
 8        while (p != null) {
 9            if (p.data.equals(value)) {
10                // 结点为头结点
11                if (p == first) {
12                    first = first.next;
13                } else if (p == last) {
14                    // 结点为尾结点
15                    last = pre;
16                } else {
17                    // 结点为中间结点
18                    pre.next = p.next;
19                }
20                size--;
21                break;
22            }
23            // 更新结点的值,向后遍历
24            pre = p;
25            p = p.next;
26        }
27    }

  根据下标删除结点和根据值删除结点类似,只需在遍历单链表时,记录下标值即可。

 1    @Override
 2    public void delete(int index) {
 3        // 首先判断下标是否合法
 4        if (index < 0 || index >= size) {
 5            return;
 6        }
 7        // 指针指向的节点的索引
 8        int i = 0;
 9        // p是遍历链表的指针
10        ListNode<T> p = first;
11        // pre记录p的前驱(前一个元素)
12        ListNode<T> pre = null;
13        while (p != null) {
14            if (i == index) {
15                // 结点为头结点
16                if (p == first) {
17                    first = first.next;
18                } else if (p == last) {
19                    // 结点为尾结点
20                    last = pre;
21                } else {
22                    // 结点为中间结点
23                    pre.next = p.next;
24                }
25                size--;
26                break;
27            }
28            // 更新结点的值,向后遍历
29            pre = p;
30            p = p.next;
31            // 下标自加
32            i++;
33        }
34    }
4)打印单链表

  重写单链表的 toString 方法,将单链表中的所有结点的值组成字符串即可。

 1    @Override
 2    public String toString() {
 3        StringBuilder sb = new StringBuilder("[");
 4        ListNode<T> p = first;
 5        // 遍历单链表
 6        while (p != null) {
 7            sb.append(p.data);
 8            p = p.next;
 9            if (p != null) {
10                sb.append(",");
11            }
12        }
13        sb.append("]");
14        return sb.toString();
15    }
5)其他方法

  其他的方法的实现比较简单,这里不多做解释,SingleLinkedList 的全部代码如下:

  1/**
  2 * 单链表
  3 **/
  4public class SingleLinkedList<T> implements MyList<T> {
  5
  6    /**
  7     * 开头(头结点)
  8     */
  9    public ListNode<T> first;
 10    /**
 11     * 结尾(尾结点)
 12     */
 13    private ListNode<T> last;
 14    /**
 15     * 链表的长度,结点的个数
 16     */
 17    private int size = 0;
 18
 19    @Override
 20    public void add(T value) {
 21        // 如果单链表为空,则将结点赋给单链表的头结点和尾结点
 22        if (first == null) {
 23            first = new ListNode<>(value);
 24            last = first;
 25        } else {
 26            // 如果单链表有结点,则直接向后追加并更新尾结点的值
 27            last.next = new ListNode<>(value);
 28            last = last.next;
 29        }
 30        // 更新单链表的长度
 31        size++;
 32    }
 33
 34    @Override
 35    public void insert(int index, T value) {
 36        // 如果下标等于0,则更换单链表的头结点
 37        if (index == 0) {
 38            ListNode<T> newNode = new ListNode<>(value);
 39            newNode.next = first;
 40            first = newNode;
 41            // 更新单链表的长度
 42            size++;
 43        } else if (index == size) {
 44            // 如果下标等于size,则是向单链表的末尾添加结点,直接调用 add 方法即可
 45            add(value);
 46        } else if (index > -1 && index < size) {
 47            // 如果下标大于-1且小于元素的个数,则表示向单链表中插入结点
 48            ListNode<T> newNode = new ListNode<>(value);
 49            // 指针指向的结点的索引
 50            int i = 0;
 51            // p是遍历链表的指针
 52            ListNode<T> p = first;
 53            // pre记录p的前驱(前一个元素)
 54            ListNode<T> pre = null;
 55            while (p != null) {
 56                // 找到结点后,将新结点的后继指向p,将p的原前驱的后继指向新结点即可
 57                if (i == index) {
 58                    pre.next = newNode;
 59                    newNode.next = p;
 60                    // 更新单链表的长度
 61                    size++;
 62                    break;
 63                }
 64                // 更新结点的值,向后遍历
 65                pre = p;
 66                p = p.next;
 67                // 下标自加
 68                i++;
 69            }
 70        }
 71    }
 72
 73    @Override
 74    public void delete(T value) {
 75        // p是遍历链表的指针
 76        ListNode<T> p = first;
 77        // pre记录p的前驱(前一个元素)
 78        ListNode<T> pre = null;
 79        // 遍历链表
 80        while (p != null) {
 81            if (p.data.equals(value)) {
 82                // 结点为头结点
 83                if (p == first) {
 84                    first = first.next;
 85                } else if (p == last) {
 86                    // 结点为尾结点
 87                    last = pre;
 88                } else {
 89                    // 结点为中间结点
 90                    pre.next = p.next;
 91                }
 92                size--;
 93                break;
 94            }
 95            // 更新结点的值,向后遍历
 96            pre = p;
 97            p = p.next;
 98        }
 99    }
100
101    @Override
102    public void delete(int index) {
103        // 首先判断下标是否合法
104        if (index < 0 || index >= size) {
105            return;
106        }
107        // 指针指向的节点的索引
108        int i = 0;
109        // p是遍历链表的指针
110        ListNode<T> p = first;
111        // pre记录p的前驱(前一个元素)
112        ListNode<T> pre = null;
113        while (p != null) {
114            if (i == index) {
115                // 结点为头结点
116                if (p == first) {
117                    first = first.next;
118                } else if (p == last) {
119                    // 结点为尾结点
120                    last = pre;
121                } else {
122                    // 结点为中间结点
123                    pre.next = p.next;
124                }
125                size--;
126                break;
127            }
128            // 更新结点的值,向后遍历
129            pre = p;
130            p = p.next;
131            // 下标自加
132            i++;
133        }
134    }
135
136    @Override
137    public void update(int index, T value) {
138        if (index < 0 || index >= size) {
139            return;
140        }
141        int i = 0;
142        ListNode<T> p = first;
143        while (p != null) {
144            if (i == index) {
145                p.data = value;
146                break;
147            }
148            p = p.next;
149            i++;
150        }
151    }
152
153    @Override
154    public boolean contains(T target) {
155        ListNode<T> p = first;
156        while (p != null) {
157            if (p.data.equals(target)) {
158                return true;
159            }
160            p = p.next;
161        }
162        return false;
163    }
164
165    @Override
166    public T at(int index) {
167        if (index < 0 || index >= size) {
168            return null;
169        }
170        int i = 0;
171        ListNode<T> p = first;
172        while (p != null) {
173            if (i == index) {
174                return p.data;
175            }
176            p = p.next;
177            i++;
178        }
179        return null;
180    }
181
182    @Override
183    public int indexOf(T value) {
184        int i = 0;
185        ListNode<T> p = first;
186        while (p != null) {
187            if (p.data.equals(value)) {
188                return i;
189            }
190            p = p.next;
191            i++;
192        }
193        return -1;
194    }
195
196    @Override
197    public String toString() {
198        StringBuilder sb = new StringBuilder("[");
199        ListNode<T> p = first;
200        // 遍历单链表
201        while (p != null) {
202            sb.append(p.data);
203            p = p.next;
204            if (p != null) {
205                sb.append(",");
206            }
207        }
208        sb.append("]");
209        return sb.toString();
210    }
211
212    @Override
213    public int getSize() {
214        return size;
215    }
216}

四、双链表

  双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

1、定义结点

  双链表的结点由前驱指针(指示前驱元素存储位置) + 元素(数据元素的映象) + 后继指针(指示后继元素存储位置)组成,由于存储的数据类型不确定,我们使用泛型来表示未确定的数据类型。

 1/**
 2 * 双链表的结点
 3 **/
 4public class ListNode<T> {
 5    
 6    /**
 7     * 存储前驱(头指针)
 8     */
 9    protected ListNode<T> pre;
10    /**
11     * 存储数据
12     */
13    protected T data;
14    /**
15     * 存储后继(尾指针)
16     */
17    protected ListNode<T> next;
18    /**
19     * 创建结点并初始化值
20     */
21    public ListNode(T data) {
22        this.data = data;
23    }
24}

2、实现双链表

  双链表与单链表最大的区别就是结点存储了前驱,为了方便操作双链表的头结点和尾结点不再存储元素称为哑元。

 1/**
 2 * 双链表
 3 **/
 4public class DoubleLinkedList<T> implements MyList<T> {
 5
 6    /**
 7     * 开头(头结点)
 8     */
 9    protected ListNode<T> first = new ListNode<>(null);
10    /**
11     * 结尾(尾结点)
12     */
13    protected ListNode<T> last = new ListNode<>(null);
14    /**
15     * 链表的长度,结点的个数
16     */
17    protected int size = 0;
18}
1)创建双链表

  创建双链表时,要为哑元的前驱或后继赋值,以免在运算时出现空指针。

1    public DoubleLinkedList() {
2        // 维护两个哑元做头尾
3        this.first.next = last;
4        this.last.pre = first;
5    }
2)添加结点

  首先将尾哑元的前驱结点的后指针指向新结点,然后将新结点的头指针和尾指针分别指向尾哑元的前驱和尾哑元,最后将尾哑元的头指针指向新结点。

 1    @Override
 2    public void add(T value) {
 3        ListNode<T> newNode = new ListNode<>(value);
 4        // 将尾哑元的前驱结点的后指针指向新结点
 5        last.pre.next = newNode;
 6        // 新结点头指针指向尾哑元的前驱
 7        newNode.pre = last.pre;
 8        // 新结点尾指针指向尾哑元
 9        newNode.next = last;
10        // 尾哑元头指针指向新结点
11        last.pre = newNode;
12        size++;
13    }
3)插入结点

  因为有哑元的存在,插入结点时无需分多种情况讨论。首先遍历双链表找到指定结点,然后将新结点的头结点和尾结点分别指向当前结点的前驱和当前结点,最后将当前结点前驱的尾结点和当前结点的头结点指向新结点。

 1    @Override
 2    public void insert(int index, T value) {
 3        if (index > -1 && index <= size) {
 4            // 如果下标大于-1且小于元素的个数,则表示向双链表中插入结点
 5            ListNode<T> newNode = new ListNode<>(value);
 6            // 指针指向的结点的索引
 7            int i = 0;
 8            // p是遍历链表的指针
 9            ListNode<T> p = first.next;
10            while (p != null) {
11                // 找到结点后,将新结点的头结点和尾结点分别指向p的前驱和p
12                // 然后更新p前驱的尾结点和p的头结点。
13                if (i == index) {
14                    newNode.pre = p.pre;
15                    newNode.next = p;
16                    p.pre.next = newNode;
17                    p.pre = newNode;
18                    // 更新单链表的长度
19                    size++;
20                    break;
21                }
22                // 更新结点的值,向后遍历
23                p = p.next;
24                // 下标自加
25                i++;
26            }
27        }
28    }
4)删除结点

  删除元素的方式分为:根据下标删除元素和根据元素值删除元素。

  根据值删除结点,首先遍历双链表查找第一个和该值相同的结点,然后将其前驱的尾结点指向当前结点的尾结点,后驱的头结点指向当前结点的头结点。

 1    @Override
 2    public void delete(T value) {
 3        ListNode<T> p = first.next;
 4        // 遍历双链表
 5        while (p != last) {
 6            if (p.data.equals(value)) {
 7                // 将上一个节点的尾指针指向下一个节点
 8                p.pre.next = p.next;
 9                // 将下一节点的头指针指向上一个节点
10                p.next.pre = p.pre;
11                // 当前指针赋空
12                p.next = null;
13                p.pre = null;
14                size--;
15                break;
16            }
17            p = p.next;
18        }
19    }

  根据下标删除结点和根据值删除结点类似,只需在遍历双链表时,记录下标值即可。

 1    @Override
 2    public void delete(int index) {
 3        if (index < 0 || index >= size) {
 4            return;
 5        }
 6        // 指针指向的节点的索引
 7        int i = 0;
 8        ListNode<T> p = first.next;
 9        while (p != last) {
10            if (i == index) {
11                // 将上一个节点的尾指针指向下一个节点
12                p.pre.next = p.next;
13                // 将下一节点的头指针指向上一个节点
14                p.next.pre = p.pre;
15                // 当前指针赋空
16                p.next = null;
17                p.pre = null;
18                size--;
19                break;
20            }
21            p = p.next;
22            i++;
23        }
24    }
5)其他方法

  其他的方法的实现和单链表相似,DoubleLinkedList 的全部代码如下:

  1/**
  2 * 双链表
  3 **/
  4public class DoubleLinkedList<T> implements MyList<T> {
  5
  6    /**
  7     * 开头(头结点)
  8     */
  9    protected ListNode<T> first = new ListNode<>(null);
 10    /**
 11     * 结尾(尾结点)
 12     */
 13    protected ListNode<T> last = new ListNode<>(null);
 14    /**
 15     * 链表的长度,结点的个数
 16     */
 17    protected int size = 0;
 18
 19    public DoubleLinkedList() {
 20        // 维护两个哑元做头尾
 21        this.first.next = last;
 22        this.last.pre = first;
 23    }
 24
 25    @Override
 26    public void add(T value) {
 27        ListNode<T> newNode = new ListNode<>(value);
 28        // 将尾哑元的前驱结点的后指针指向新结点
 29        last.pre.next = newNode;
 30        // 新结点头指针指向尾哑元的前驱
 31        newNode.pre = last.pre;
 32        // 新结点尾指针指向尾哑元
 33        newNode.next = last;
 34        // 尾哑元头指针指向新结点
 35        last.pre = newNode;
 36        size++;
 37    }
 38
 39    @Override
 40    public void insert(int index, T value) {
 41        if (index > -1 && index <= size) {
 42            // 如果下标大于-1且小于元素的个数,则表示向双链表中插入结点
 43            ListNode<T> newNode = new ListNode<>(value);
 44            // 指针指向的结点的索引
 45            int i = 0;
 46            // p是遍历链表的指针
 47            ListNode<T> p = first.next;
 48            while (p != null) {
 49                // 找到结点后,将新结点的头结点和尾结点分别指向p的前驱和p
 50                // 然后更新p前驱的尾结点和p的头结点。
 51                if (i == index) {
 52                    newNode.pre = p.pre;
 53                    newNode.next = p;
 54                    p.pre.next = newNode;
 55                    p.pre = newNode;
 56                    // 更新单链表的长度
 57                    size++;
 58                    break;
 59                }
 60                // 更新结点的值,向后遍历
 61                p = p.next;
 62                // 下标自加
 63                i++;
 64            }
 65        }
 66    }
 67
 68    @Override
 69    public void delete(T value) {
 70        ListNode<T> p = first.next;
 71        // 遍历双链表
 72        while (p != last) {
 73            if (p.data.equals(value)) {
 74                // 将上一个节点的尾指针指向下一个节点
 75                p.pre.next = p.next;
 76                // 将下一节点的头指针指向上一个节点
 77                p.next.pre = p.pre;
 78                // 当前指针赋空
 79                p.next = null;
 80                p.pre = null;
 81                size--;
 82                break;
 83            }
 84            p = p.next;
 85        }
 86    }
 87
 88    @Override
 89    public void delete(int index) {
 90        if (index < 0 || index >= size) {
 91            return;
 92        }
 93        // 指针指向的节点的索引
 94        int i = 0;
 95        ListNode<T> p = first.next;
 96        while (p != last) {
 97            if (i == index) {
 98                // 将上一个节点的尾指针指向下一个节点
 99                p.pre.next = p.next;
100                // 将下一节点的头指针指向上一个节点
101                p.next.pre = p.pre;
102                // 当前指针赋空
103                p.next = null;
104                p.pre = null;
105                size--;
106                break;
107            }
108            p = p.next;
109            i++;
110        }
111    }
112
113    @Override
114    public void update(int index, T value) {
115        if (index < 0 || index >= size) {
116            return;
117        }
118        int i = 0;
119        ListNode<T> p = first.next;
120        while (p != last) {
121            if (i == index) {
122                p.data = value;
123                break;
124            }
125            p = p.next;
126            i++;
127        }
128    }
129
130    @Override
131    public boolean contains(T target) {
132        ListNode<T> p = first.next;
133        while (p != last) {
134            if (p.data.equals(target)) {
135                return true;
136            }
137            p = p.next;
138        }
139        return false;
140    }
141
142    @Override
143    public T at(int index) {
144        if (index < 0 || index >= size) {
145            return null;
146        }
147        int i = 0;
148        ListNode<T> p = first.next;
149        while (p != last) {
150            if (i == index) {
151                return p.data;
152            }
153            p = p.next;
154            i++;
155        }
156        return null;
157    }
158
159    @Override
160    public int indexOf(T value) {
161        int i = 0;
162        ListNode<T> p = first.next;
163        while (p != last) {
164            if (p.data.equals(value)) {
165                return i;
166            }
167            p = p.next;
168            i++;
169        }
170        return -1;
171    }
172
173    @Override
174    public String toString() {
175        StringBuilder sb = new StringBuilder("[");
176        ListNode<T> p = first.next;
177        while (p != last) {
178            sb.append(p.data);
179            p = p.next;
180            if (p != last) {
181                sb.append(",");
182            }
183        }
184        sb.append("]");
185        return sb.toString();
186    }
187
188    @Override
189    public int getSize() {
190        return size;
191    }
192}

标题:使用链式存储结构实现线性表(单链表、双链表)
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2020/03/01/1583073649918.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!