数学建模社区-数学中国

标题: 【Java演示】什么是链表？数据结构 [打印本页]

作者: 杨利霞 时间: 2020-5-4 15:55
标题: 【Java演示】什么是链表？数据结构

【Java演示】什么是链表？数据结构
一、单向链表

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。
链表的第1个节点被称为头节点，最后1个节点被称为尾节点，尾节点的next指针指向空。

什么叫随机存储呢？

如果说数组在内存中的存储方式是顺序存储，那么链表在内存中的存储方式则是随机存储。
上一节我们讲解了数组的内存分配方式，数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式，链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

图中的箭头代表链表节点的next指针。

链表的基本操作1. 查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。

/**
   * 链表查找元素
   *
   * @param index 查找的位置
   * @return index位置的Node对象
   */
public Node get(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表的节点的范围！");
      }
      Node temp = head;
      for (int i = 0; i < index; i++) {
         temp = temp.next;
      }
      return temp;
}

链表中的数据只能按顺序进行访问，最坏的时间复杂度是O(n)

2. 更新节点

如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可。
如果不考虑查找元素的过程，只考虑纯粹的更新节点操作，时间复杂度是O(1)
/**
   * 更新节点将列表中指定位置的节点的data替换为指定的data。
   *
   * @param index 需要更新的节点的位置
   * @param data  新data
   * @return 旧data
   */
public int set(int index, int data) {
      Node x = get(index);
      int oldVal = x.data;
      x.data = data;
      return oldVal;
}

3. 插入节点

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

与数组类似，链表插入节点时，同样分为3种情况。

尾部插入
头部插入
中间插入
4 q$ P' [$ S. D0 C2 m0 T! U9 K

3.1. 尾部插入

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。

3.2. 头部插入

头部插入，可以分成两个步骤。

第1步，把新节点的next指针指向原先的头节点。
第2步，把新节点变为链表的头节点。
% A& [0 s. l* Q7 [1 f% ~5 i

3.3. 中间插入

中间插入，同样分为两个步骤。

第1步，新节点的next指针，指向插入位置的节点。
第2步，插入位置前置节点的next指针，指向新节点。7 W4 d2 g f) o8 i/ f: k

三钟情况的代码合到一起

/**
   * 链表插入元素
   *
   * @param index 插入位置
   * @param data  插入元素被插入的链表节点的数据
   */
public void insert(int index, int data) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表节点范围！");
      }
      Node insertedNode = new Node(data);
      if (size == 0) {
         //空链表
         head = insertedNode;
         last = insertedNode;
      } else if (index == 0) {
         //插入头部
         insertedNode.next = head;
         head = insertedNode;
      } else if (size == index) {
         //插入尾部
         last.next = insertedNode;
         last = insertedNode;
      } else {
         //插入中间
         Node prvNode = get(index - 1);
         insertedNode.next = prvNode.next;
         prvNode.next = insertedNode;
      }
      size++;
}

/**
   * 链表插入元素
   *
   * @param index 插入位置
   * @param data  插入元素被插入的链表节点的数据
   */
public void insert(int index, int data) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表节点范围！");
      }
      Node insertedNode = new Node(data);
      if (size == 0) {
         //空链表
         head = insertedNode;
         last = insertedNode;
      } else if (index == 0) {
         //插入头部
         insertedNode.next = head;
         head = insertedNode;
      } else if (size == index) {
         //插入尾部
         last.next = insertedNode;
         last = insertedNode;
      } else {
         //插入中间
         Node prvNode = get(index - 1);
         insertedNode.next = prvNode.next;
         prvNode.next = insertedNode;
      }
      size++;
}
4. 删除元素

链表的删除操作同样分为3种情况。

尾部删除
头部删除
中间删除
0 U3 W+ @' r; H( T2 t

4.1. 尾部删除

尾部删除，是最简单的情况，把倒数第2个节点的next指针指向空即
" _; n [) d* B$ ?6 D# O9 J% y可。

4.1. 头部删除

头部删除，也很简单，把链表的头节点设为原先头节点的next指针即可。

4.1. 中间删除

中间删除，同样很简单，把要删除节点的前置节点的next指针，指向要$ Z' I% b3 c4 a
删除元素的下一个节点即可。

这里需要注意的是，许多高级语言，如Java，拥有自动化的垃圾回收机制，所以我们不用刻意去释放被删除的节点，只要没有外部引用指向它们，被删除的节点会被自动回收。
如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入和删除操作，时间复杂度都是O(1)
/**
   * 链表删除元素
   *
   * @param index 删除的位置
   * @return 被删除的节点
   */
public Node remove(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表节点范围");
      }
      Node removeNode;
      if (index == 0) {
         if (size == 0) {
            throw new NullPointerException("当前链表为空，不可以进行删除操作");
         }
         //删除头节点
         removeNode = head;
         head = head.next;
      } else if (index == size - 1) {
         //删除尾节点
         Node preNode = get(index - 1);
         removeNode = preNode.next;
         preNode.next = null;
         last = preNode;
      } else {
         //删除中间节点
         Node prevNode = get(index - 1);
         removeNode = prevNode.next;
         prevNode.next = prevNode.next.next;
      }
      size--;
      return removeNode;
}
Java实现链表的完整代码package chapter2.part2;

/**
* Created by IntelliJ IDEA.
*
* @Author: 张志浩  Zhang Zhihao
* @Email: 3382885270@qq.com
* @Date: 2020/5/3
* @Time: 13:39
* @Version: 1.0
*/
public class MyLinkedList2 {
private Node head; //头节点
private Node last; //尾节点
private int size; //链表实际长度

public static void main(String[] args) {
      MyLinkedList2 myLinkedList = new MyLinkedList2();
//       myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空，不可以进行删除操作
//       myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围
      myLinkedList.insert(0, 3);
      myLinkedList.insert(1, 7);
      myLinkedList.insert(2, 9);
      myLinkedList.insert(3, 5);
      myLinkedList.insert(1, 6);
      myLinkedList.remove(0);
      myLinkedList.set(0, 23);
      myLinkedList.output();
}

/**
   * 链表插入元素
   *
   * @param index 插入位置
   * @param data  插入元素被插入的链表节点的数据
   */
public void insert(int index, int data) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表节点范围！");
      }
      Node insertedNode = new Node(data);
      if (size == 0) {
         //空链表
         head = insertedNode;
         last = insertedNode;
      } else if (index == 0) {
         //插入头部
         insertedNode.next = head;
         head = insertedNode;
      } else if (size == index) {
         //插入尾部
         last.next = insertedNode;
         last = insertedNode;
      } else {
         //插入中间
         Node prvNode = get(index - 1);
         insertedNode.next = prvNode.next;
         prvNode.next = insertedNode;
      }
      size++;
}

/**
   * 链表删除元素
   *
   * @param index 删除的位置
   * @return 被删除的节点
   */
public Node remove(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表节点范围");
      }
      Node removeNode;
      if (index == 0) {
         if (size == 0) {
            throw new NullPointerException("当前链表为空，不可以进行删除操作");
         }
         //删除头节点
         removeNode = head;
         head = head.next;
      } else if (index == size - 1) {
         //删除尾节点
         Node preNode = get(index - 1);
         removeNode = preNode.next;
         preNode.next = null;
         last = preNode;
      } else {
         //删除中间节点
         Node prevNode = get(index - 1);
         removeNode = prevNode.next;
         prevNode.next = prevNode.next.next;
      }
      size--;
      return removeNode;
}

/**
   * 更新节点将列表中指定位置的节点的data替换为指定的data。
   *
   * @param index 需要更新的节点的位置
   * @param data  新data
   * @return 旧data
   */
public int set(int index, int data) {
      Node x = get(index);
      int oldVal = x.data;
      x.data = data;
      return oldVal;
}

/**
   * 链表查找元素
   *
   * @param index 查找的位置
   * @return index位置的Node对象
   */
public Node get(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表的节点的范围！");
      }
      Node temp = head;
      for (int i = 0; i < index; i++) {
         temp = temp.next;
      }
      return temp;
}

/**
   * 输出链表
   */
public void output() {
      Node temp = head;
      while (temp != null) {
         System.out.print(temp.data + " ");
         temp = temp.next;
      }
}

/**
   * 链表节点
   */
class Node {
      int data;
      Node next;

      Node(int data) {
         this.data = data;
      }
}
}

二、双向链表

双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev 指针。

————————————————
版权声明：本文为CSDN博主「爱做梦的鱼」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43124279/article/details/105904468

2.png (256.36 KB, 下载次数: 272)

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)