目录
链表
链表就是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
也是线性表。
数据域:存储数据元素信息的域。
指针域:存储直接后继的信息。
链表 " />
链表的分类
链表根据三个条件分类:
- 有头无头:有没有头结点,头结点的数据域是无用的。
- 是否循环:尾结点又指回头。
- 单向还是双向:指针域包不包含指向前面域的指针。
根据以上3个条件来分类(每一个条件选一),链表一共有8种。
单链表
单链表接口的实现
自己实现一个单链表(存储int数据类型),将单链表作为一个类,我们实现一些“接口”即成员方法来实现数据的增删查改。
java">// 1、无头单向非循环链表实现public class SingleLinkedList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();//清空链表public void clear();}
内部类
因为我们需要使用数据域,指针域,在链表中一个一个串起来。那我们就将数据域指针域使用一个静态内部类来封装。只将第一个节点用head来表示。
注意:此处的head不是链表分类时的头,因为分类的头的数据域的数据是无效的而此处是有效的。
java">public class SingleLinkedList {static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;
}
头插法
实现思路:
将当前节点的下一个节点(next)指向头(head),再改头为当前节点。
java">public void addFirst(int data) {ListNode cur = new ListNode(data);cur.next = head;head = cur;}
尾插法
实现思路:
java">public void addLast(int data){if(head == null){head = new ListNode(data);}ListNode cur = head;while(cur.next != null){cur = cur.next;}cur.next = new ListNode(data);}
任意位置插入
实现思路:
- 先判断插入位置合法吗,不合法就抛异常。
- 头尾位置插入调用头插尾插函数即可。
- 中间节点插入找到前一个位置记录下来,当前位置记录下来, 在改插入节点和前一个节点的next。
java">public boolean addIndex(int index,int data) throws IndexIllegalException{try{if(index < 0 || index > size()){throw new IndexIllegalException("位置不合法");} else if (index == 0) {addFirst(data);return true;} else if (index == size()) {addLast(data);return true;}else{ListNode cur = head;ListNode pre = head;ListNode newNode = new ListNode(data);for (int i = 0; i < index-1; i++) {cur = cur.next;pre = pre.next;}newNode.next = cur.next;pre.next = cur;return true;}}catch(IndexIllegalException e){e.printStackTrace();return false;}}
查找是否包含关键字key是否在单链表当中
使用循环遍历即可。
java">public boolean contains(int key){ListNode cur = head;for (int i = 0; i < size(); i++) {if(cur.val == key){return true;}cur = cur.next;}return false;}
删除第一次出现关键字为key的节点
实现思路:
- 看链表是否为空,空直接返回。
- 先看头结点是不是要删的节点(因为删除会涉及被删节点的前一个节点),是直接将头指向下一个节点。
- 循环找到当前节点,让前一个节点next指向当前节点的next即可。
java">public void remove(int key){if(head == null){return;} else if (head .val == key) {head = head.next;return;}ListNode cur = head.next;ListNode pre = head;while(cur != null){if(cur.val == key){pre.next = cur.next;return;}cur = cur.next;pre = pre.next;}}
删除所有值为key的节点
跟删除一个节点一个逻辑只不过删除后不返回,并且头结点最后判断。
java"> public void removeAllKey(int key){if(head == null){return;}ListNode cur = head.next;ListNode pre = head;while(cur != null){if(cur.val == key){pre.next = cur.next;cur = cur.next;}else {cur = cur.next;pre = pre.next;}}if(head.val == key){head = head.next;}}
得到单链表的长度
直接循环遍历就行。
java">public int size(){ListNode cur = head;int size = 0;while(cur != null){cur = cur.next;size++;}return size;}
清空链表
直接循环将每一个节点置空,注意置空前要将头先向后走。
java">public void clear(){ListNode cur = head;while (cur != null){head = cur.next;cur = null;cur = head;}}
单链表的优缺点
优缺点如下:
- 优点:单向链表增加删除节点简单。
- 缺点:只能从头到尾遍历,只能找到后继。
双向链表
在Java的集合类中使用的是无头双向非循环链表。
链表
" />
双向链表接口的实现
自己实现一个双向链表(存储int数据类型),将双向链表作为一个类,我们实现一些“接口”即成员方法来实现数据的增删查改。
java"> // 2、无头双向链表实现public class LinkedList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到链表的长度public int size();//情空链表public void clear();}
内部类
因为我们需要使用数据域,指针域,在链表中一个一个串起来。那我们就将数据域指针域使用一个静态内部类来封装。只将第一个节点用head来表示,最后一个节点用last表示。
注意:此处的head不是链表分类时的头,因为分类的头的数据域的数据是无效的而此处是有效的。
java">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;
头插法
实现思路:
- 如果当前链表为空就直接将头尾指向当前节点。
- 如果不是先将插入节点的下一个指向头,头的前一个指向插入节点,头指向插入节点。
java"> public void addFirst(int data){ListNode cur = new ListNode(data);if(head == null){head = last = cur;return;}cur.next = head;head.prev = cur;head = cur;}
尾插法
实现思路:
java">public void addLast(int data){ListNode cur = new ListNode(data);if(last == null){head = last = cur;return;}last.next = cur;cur.prev = last;last = cur;}
任意位置插入
实现思路:
- 判断位置是否合法,不合法抛异常。
- 插入位置为头尾,对应调用头插方法,尾插方法。
- 找到插入位置对应节点,将插入节点前驱prev改为对应节点前驱,对应节点前驱改为插入节点,插入节点后继next改为对应节点。
java">public boolean addIndex(int index,int data) throws IndexIllegalException{try{if(index < 0 || index > size()){throw new IndexIllegalException("插入位置不合法");} else if (index == 0) {addFirst(data);return true;} else if (index == size()) {addLast(data);return true;}else {ListNode cur = head;ListNode newNode = new ListNode(data);for (int i = 0; i < index; i++) {cur = cur.next;}newNode.prev = cur.prev;cur.prev = newNode;newNode.next = cur;return true;}}catch (IndexIllegalException e){e.printStackTrace();return false;}}
查找是否包含关键字key是否在单链表当中
直接循环遍历就行。
java">public boolean contains(int key){ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}
删除第一次出现关键字为key的节点
实现思路:
- 先判断头节点是不是要删的节点,是将下一个节点前驱prev置为空,头指向下一个节点,返回。
- 循环遍历除头尾节点外的节点,找到被删节点,将该节点前一个节点的后继next改为该节点的下一个节点,该节点后一个节点的前驱prev改为该节点的前一个,返回。
- 如果都不是,判断尾节点,将尾结点的前一个节点的后继next置为空,尾结点改为前一个节点,返回。
java">public void remove(int key){ListNode cur = head;if(head.val == key){head.next.prev = null;head = head.next;return;} else {while(cur.next != null){if(cur.val == key){cur.prev.next = cur.next;cur.next.prev = cur.prev;return;}cur = cur.next;}if (last.val == key) {last.prev.next = null;last = last.prev;return;}}}
删除所有值为key的节点
- 先循环遍历除头尾节点外的节点,找到被删节点,将该节点前一个节点的后继next改为该节点的下一个节点,该节点后一个节点的前驱prev改为该节点的前一个。
- 判断头节点是不是要删的节点,是将下一个节点前驱prev置为空,头指向下一个节点。
- 判断尾节点,将尾结点的前一个节点的后继next置为空,尾结点改为前一个节点。
java">public void removeAllKey(int key){ListNode cur = head.next;while(cur.next != null){if(cur.val == key){cur.prev.next = cur.next;cur.next.prev = cur.prev;}cur = cur.next;}if(head.val == key){head.next.prev = null;head = head.next;}if (last.val == key) {last.prev.next = null;last = last.prev;}}
得到链表的长度
直接循环遍历即可。
java">public int size(){ListNode cur = head;int size = 0;while(cur != null){size++;cur = cur.next;}return size;}
清空链表
实现思路:
- 先循环遍历将每一个节点前驱prev后继next置为空。
- 最后将头head和为last置为空。
java">public void clear(){ListNode cur = head;while(cur != null){ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}head = null;last = null;}
}
Java中的LinkedList
在Java中用集合类LinkedList来表示双向链表。
实现的接口
接口说明:
- 没有实现RandomAccess接口,不能随机访问。
- 实现了Cloneable接口,可克隆。
- Serializable接口表示支持序列化。
构造方法
Java中提供了两个构造方法。
方法 | 方法用途介绍 |
---|---|
LinkedList() | 无参构造 |
public LinkedList(Collection<? extends E> c) | 使用其他集合容器中元素构造List |
常用方法
提供的常用方法与上面实现的差不多。
双向链表的优劣
优缺点如下:
- 优点:可以找到前驱和后继,可进可退。
- 确点:删除节点复杂,需要多分配一个指针域。
ArrayList和LinkedList对比
对比如下图:
链表练习
删除链表中等于给定值 val 的所有节点
反转一个单链表
链表的中间节点
合并两个有序链表
链表分割
链表的回文结构
相交链表
环形链表