数据结构基础之链表

目录

前言

1、什么是链表

2、添加元素

3、虚拟头结点

4、查询&修改元素

5、删除元素

附：完整代码

---

前言

又到周末了，修整了一天，继续来写点东西吧，今天，我们来学习数据结构中的另一种基础的数据结构——链表。话不多说，开整吧！

1、什么是链表

在说链表之前，先来看一下我们之前说的动态数组、栈、队列这几种数据结构，它们的底层都是依托于静态数组，都是靠resize解决固定容量问题。而今天要说的链表，它和上述几种数据结构都不同，它是真正的动态数据结构，也是最简单的动态数据结构，同时它会涉及到计算机领域一个很重要的概念——引用（或者指针），理解链表能够帮助我们更深入的理解引用这个概念。

链表：数据存储在“节点”（Node）中

class Node {// 存储真正的数据E e; // next是Node类型的对象，即：next本身又是一个节点，指向的是当前节点的下一个节点Node next; 
}

链表就像火车，每个节点就是一节车厢，车厢中存储真正的数据，车厢和车厢之间进行连接，使得数据整合在一起，用户可以方便的在数据上进行查询等操作。

优点：真正的动态，不需要处理固定容量的问题

缺点：丧失了随机访问的能力

2、添加元素

定义链表类LinkedList且定义为泛型类，然后定义它的内部类Node这个节点类，并且定义两个成员变量：头结点和链表的长度。我们分别实现了在链表头部、链表中间及链表尾部添加节点的操作，代码实现如下：

public class LinkedList<E> {private Node head;private int size;public LinkedList() {head = null;size = 0;}// 获取链表中的元素个数public int getSize() {return size;}// 返回链表是否为空public boolean isEmpty() {return size == 0;}// 在链表头添加新的元素public void addFirst(E e) {
//        Node node = new Node(e);
//        node.next = head;
//        head = node;head = new Node(e, head);size++;}// 在链表中间添加元素public void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("添加失败，位置错误");}if (index == 0) {addFirst(e);} else {Node prev = head;for (int i = 0; i < index - 1; i++) {prev = prev.next;}
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;prev.next = new Node(e, prev.next);size++;}}// 在链表末尾添加元素public void addLast(E e) {add(size, e);}private class Node {public E e;public Node next;public Node(E e, Node next) {this.e = e;this.next = next;}public Node(E e) {this(e, null);}public Node() {this(null, null);}@Overridepublic String toString() {return e.toString();}}
}

3、虚拟头结点

我们知道在向链表头添加元素和向链表其它位置添加元素是有区别的，因为我们在添加元素时需要找到待添加元素位置之前的一个节点，对于链表头来说，它没有前一个位置的节点，所以才会显得比较特殊，因此，通常来说有一种技巧可以实现对于链表头添加元素和其它位置添加元素的操作统一起来，就是在链表头节点之前再造一个节点，该节点不存储任何元素，我们称之为虚拟头结点——dummyHead，这样对于链表来说它的第一个元素就是dummyHead的next所对应节点的元素（注意dummyHead这个位置对应的元素是根本不存在的，仅仅是为了逻辑上的统一）。

public class LinkedList<E> {private Node dummyHead;private int size;public LinkedList() {dummyHead = new Node(null, null);size = 0;}// 在链表中间添加元素public void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("添加失败，位置错误");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;prev.next = new Node(e, prev.next);size++;}// 在链表头添加新的元素public void addFirst(E e) {add(0, e);}// 在链表末尾添加元素public void addLast(E e) {add(size, e);}
}

4、查询&修改元素

查询：

修改：

判断链表中是否包含某个元素：

下面来写个测试方法简单测试一下：

执行结果如下：

5、删除元素

 

在上一部分的测试代码中，我们稍作修改：

可以看到，我们也得到了想要的结果：

OK，关于链表的增删改查就已经都说完了，今天就先到这里吧，再会！

祝：工作顺利！

附：完整代码

public class LinkedList<E> {private Node dummyHead;private int size;public LinkedList() {dummyHead = new Node(null, null);size = 0;}// 获取链表中的元素个数public int getSize() {return size;}// 返回链表是否为空public boolean isEmpty() {return size == 0;}// 在链表中间添加元素public void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("添加失败，位置错误");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;prev.next = new Node(e, prev.next);size++;}// 在链表头添加新的元素public void addFirst(E e) {add(0, e);}// 在链表末尾添加元素public void addLast(E e) {add(size, e);}// 获取链表的第index位置的元素（索引在链表中是非常用操作，仅做练习使用）public E get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("获取失败，位置错误");}Node cur = dummyHead.next;for (int i = 0; i < index; i++) {cur = cur.next;}return cur.e;}// 获取链表的第一个元素public E getFirst() {return get(0);}// 获取链表的最后一个元素public E getLast() {return get(size - 1);}// 修改链表的第index位置的元素public void set(int index, E e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("设置失败，位置错误");}Node cur = dummyHead.next;for (int i = 0; i < index; i++) {cur = cur.next;}cur.e = e;}// 查找链表中是否有元素epublic boolean contains(E e) {Node cur = dummyHead.next;while (cur != null) {if (cur.e.equals(e)) {return true;}cur = cur.next;}return false;}// 从链表中删除index位置的元素，返回删除的元素public E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("删除失败，位置错误");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}Node retNode = prev.next;prev.next = retNode.next;retNode.next = null;size--;return retNode.e;}// 删除第一个元素public E removeFirst() {return remove(0);}// 删除最后一个元素public E removeLast() {return remove(size - 1);}@Overridepublic String toString() {StringBuilder res = new StringBuilder();for (Node cur = dummyHead.next; cur != null; cur = cur.next) {res.append(cur + "->");}res.append("NULL");return res.toString();}private class Node {public E e;public Node next;public Node(E e, Node next) {this.e = e;this.next = next;}public Node(E e) {this(e, null);}public Node() {this(null, null);}@Overridepublic String toString() {return e.toString();}}
}