线性表的链式存储——链表

目录

1.概念

2.链表

2.1 单链表概念及结构

2.2双链表的概念及结构

2.3 循环链表 

3.链表的具体使用

4.自己实现链表及方法：

双链表：

单链表：

1.概念

        链式存储是常用的动态存储方式，相对于顺序表，可以更好的任意插入与删除，而采用链式存储的结构叫做链表。

        链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。      

        从链接方式的角度：链表分为单链表、双链表及循环链表；

        从实现方式的角度：链表分为动态链表和静态链表；

2.链表

2.1 单链表概念及结构

 概念：

        单链表是通过一个一个结点进行连接，而链表并不像顺序表一样存储的是一组地址连续的存储单元，而是非连续的。因此，链表中的结点不仅需要存储自己的数据元素值（数据域），还需要存储下一个结点的地址（指针域）。

 结构：

        单链表的每个结点的地址都存储在其前驱结点的指针域中，因此第一个结点无前驱，这个时候我们可以设置一个头指针Head指向第一个结点。而最后一个结点后面没有结点，所以最后一个结点指针域为空（Null）。

 单链表结构：

2.2双链表的概念及结构

概念：

        每个结点相对与单链表多了一个指针域，其它与单链表基本相同。

结构：

2.3 循环链表 

概念：

        循环链表是建立在单链表和双链表的基础上，将头尾相连，形成一个环，这就是循环链表，可分为：循环单链表、循环双链表。

3.链表的具体使用

 代码实现：

public class Test1 {public static void main(String[] args) {System.out.println(list.add(1));//尾插1，Booleanlist.addFirst(2);//头插2System.out.println(list);list.addLast(3);//尾插3System.out.println(list);list.add(1,4);//1坐标插入4System.out.println(list);list.remove(2);//删除2坐标元素System.out.println(list);System.out.println(list.get(2));//获得2坐标元素System.out.println(list);list.set(1,3);//将1坐标元素改为3System.out.println(list);System.out.println(list.contains(3));//是否含5System.out.println(list.contains(6));//是否含6System.out.println(list.indexOf(3));//第一个3的下标System.out.println(list.lastIndexOf(3));//最后一个3的下标System.out.println(list.subList(0,1));//截取[0,1)的list，前闭后开System.out.println(list.isEmpty());//list中是否有元素list.clear();//清空System.out.println(list.isEmpty());}
}

运行结果：

true
[2, 1]
[2, 1, 3]
[2, 4, 1, 3]
[2, 4, 3]
3
[2, 4, 3]
[2, 3, 3]
true
false
1
2
[2]
false
true

4.自己实现链表及方法：

注意：

        上面这些方法的实现，我们可以直接用，但是我们也可以创建自己的链表，实现自己的方法，让我们更好的理解，提升我们的代码能力。

        代码的实现我放在了下面，但是最好自己实现一遍。

双链表：

public class MyLinkedList {static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//头插法public void addFirst(int data){ListNode listNode = new ListNode(data);if (head == null){head = listNode;last = listNode;}else{head.prev = listNode;listNode.next = head;head = listNode;}}//尾插法public void addLast(int data){ListNode listNode = new ListNode(data);if(last == null){last = listNode;head = listNode;}else{last.next = listNode;listNode.prev = last;last = listNode;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){ListNode listNode = new ListNode(data);if(index < 0 || index > size()){System.out.println("不合法");return;}if(index == 0){addFirst(data);return;}if (index == size()){addLast(data);return;}ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}listNode.next = cur;cur.prev.next = listNode;listNode.prev = cur.prev;cur.prev = listNode;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if(cur.val == key){return true;}}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;while (cur != null){if(cur.val == key){if(cur == head){head = head.next;}else{if (cur.next == null) {cur.prev.next = null;last = cur.prev;}else{cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}else{cur = cur.next;}}System.out.println("没有这个节点");}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;while (cur != null){if(cur.val == key){if(cur == head){head = head.next;}else{if (cur.next == null) {cur.prev.next = null;last = cur.prev;}else{cur.prev.next = cur.next;cur.next.prev = cur.prev;}}}cur = cur.next;}}//得到单链表的长度public int size(){int count = 0;ListNode cur = head;while (cur != null){count++;cur = cur.next;}return count;}public void display(){ListNode cur = head;while (cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}public void clear(){head = null;}
}

单链表：

public class SingleLinkedList {class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public void createNode(){ListNode listNode1 = new ListNode(12);ListNode listNode2 = new ListNode(23);ListNode listNode3 = new ListNode(34);ListNode listNode4 = new ListNode(45);ListNode listNode5 = new ListNode(45);head = listNode1;listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;}public ListNode head;//打印public void show(){ListNode cur = head;for (int i = 0; i < size(); i++) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//长度public int size(){ListNode cur = head;int count = 0;while(cur != null){cur = cur.next;count++;}return count;}//查找public boolean contains(int key){ListNode cur = head;if(cur == null){return false;}while (cur.val != key){if(cur.next == null){return false;}cur = cur.next;}return true;}//头插public void addFirst(int data){ListNode newNode = new ListNode(data);newNode.next = head;head = newNode;}//尾插public void addLast(int data){ListNode newNode = new ListNode(data);ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = newNode;}//随意插public void addIndex(int index,int data){ListNode cur = head;ListNode newNode = new ListNode(data);if(index == 0){addFirst(data);return;}if(index < 0 || index > size() || cur == null){throw new IndexOutOfBounds("数组不合法，越界: " + index);}if(index == size()){addLast(data);return;}for (int i = 1; i < index; i++) {cur = cur.next;}newNode.next = cur.next;cur.next = newNode;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;ListNode pver = head;if(cur == null){System.out.println("链表无节点");return;}if(cur.val == key){head = head.next;}while(cur.val != key){if(cur.next == null){System.out.println("无此节点");return;}pver = cur;cur = cur.next;}if(cur.val == key){pver.next = cur.next;return;}}//删除所有值为key的节点public void removeAllKey(int key){if(head == null) {return;}ListNode cur = head.next;ListNode prev = head;while (cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val ==  key) {head = head.next;}}//清除所有数据public void clear(){head = null;}
}