目录
1.介绍
链表也是线性表的一种，是一种物理存储结构上非连续存储的存储结构，其中数据元素的逻辑顺序通过链表中的引用链接次序实现。链表的结构非常多样，可以是单向的或多向，带头或不带头的，循环或非循环的
2.链表实现
链表的实现可以通过自己写代码实现(主要介绍不带头非循环单链表和不带头非循环多链表)，或者和实现顺序表的时候一样直接使用List接口实现
2.1 简单实现单链表SingleList
SingleList的结点类由两个部分组成，分别是val(存储的值)和next(该结点的下一个结点的地址)，每个结点的地址都是随机的，当结点的值为null时，表示该结点没有下一个结点
public class MySingleList { // 不带头非循环单链表
static class ListNode { //静态内部类实现SingleList的结点类
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
ListNode head;
public void addFirst(int data) { //头插法
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}
public void addLast(int data) { //尾插法
ListNode node = new ListNode(data);
if (head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
public void addIndex(int index, int data) throws IndexException { //任意位置插入,第一个数据节点为0号下标
if (index < 0 || index > this.size()) {
throw new IndexException("index的值不合法:" + index);
}
if (index == 0) {
addFirst(data);
return;
}
if (index == this.size()) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = this.head;
for (int i = 0; i < index - 1; i++) {
cur = cur.next;
}
node.next = cur.next;
cur.next = node;
}
public boolean contains(int key) { //查找是否包含关键字key是否在单链表当中
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
}
return false;
}
public void remove(int key) { //删除第一次出现关键字为key的结点
if (head == null) {
return;
}
if (head.val == key) {
head = head.next;
return;
}
ListNode prev = findPrevKey(key);
if (prev == null) {
return;
}
prev.next = prev.next.next;
}
public ListNode findPrevKey(int key){
ListNode cur = this.head;
while(cur.next != null){
if(cur.next.val == key){
return cur;
}else{
cur = cur.next;
}
}
return null;
}
public void removeAllKey(int key) { //删除所有值为key的结点
if (head == null) {
return;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
if(this.head.val == key){
this.head = this.head.next;
}
}
public int size() { //得到单链表的长度
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void clear() {
this.head = null;
}
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.println(cur.val);
cur = cur.next;
}
}
}
2.2 简单实现双链表LinkedList
不同于单链表，双链表LinkedList的结点类由三个部分组成，分别是val(存储的值)，prev(该结点的上一个结点的地址)和next(该结点的下一个结点的地址)
public class MyLinkedList { //不带头非循环双链表
static class ListNode { //静态内部类实现LinkedList的结点类
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
public void addFirst(int data) { //头插法
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
}
public void addLast(int data) { //尾插法
ListNode node = new ListNode(data);
if (head == null) {
head = node;
}else{
last.next = node;
node.prev = last;
last = node;
}
}
public void addIndex(int index, int data) throws IndexException { //任意位置插入,第一个数据节点为0号下标
if(index < 0 || index > size()){
throw new IndexException("index值不合法:"+index);
}
if(index == 0){
addFirst(data);
}
if(index == size()){
addLast(data);
}
ListNode node = new ListNode(data);
ListNode cur = this.head;
for(int i=0;i < index;i++){
cur = cur.next;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
public boolean contains(int key) { //查找是否包含关键字key是否在单链表当中
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
public void remove(int key) { //删除第一次出现关键字为key的结点
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
if(cur == this.head){ //删除头结点
head = head.next;
if(head != null){
head.prev = null;
}else {
last = null;
}
}else{
if(cur.next != null){ //删除中间结点
cur.next.prev = cur.next;
}else{ //删除尾结点
last = last.prev;
}
cur.prev.next = cur.next;
}
return;
}
cur = cur.next;
}
}
public void removeAllKey(int key) { //删除所有值为key的结点
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
if(cur == this.head){
head = head.next;
if(head != null){
head.prev = null;
}else {
last = null;
}
}else{
if(cur.next != null){
cur.next.prev = cur.next;
}else{
last = last.prev;
}
cur.prev.next = cur.next;
}
}
cur = cur.next;
}
}
public int size() { //得到单链表的长度
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.println(cur.val);
cur = cur.next;
}
}
public void clear() {
this.head = null;
this.last = null;
}
}
2.3 List接口实现链表
LinkedList的底层是双链表结构，所以创建出来的链表是双链表
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
//LinkedList实现了List接口(以下两种实现方式都可以,根据创建的list的类型进行选择)
LinkedList<Integer> list1 = new LinkedList<>();
List<Integer> list2 = new LinkedList<>();
}
}
3.LinkedList的常用方法
| 方法 | 解释 |
|---|---|
| LinkedList( ) | 无参构造 |
| public LinkedList(Collection<? extends E> c) | 使用其他集合容器元素构造list |
| boolean add(E e) | 尾插e |
| void add(int index,E element) | 将e插入到index位置 |
| boolean addAll(Collection<? extends E> c) | 尾插c中的元素 |
| E remove(int index) | 删除index位置元素 |
| boolean remove(Object o) | 删除遇到的第一个o |
| E get(int index) | 获取下标index位置元素 |
| E set(int index,E element) | 将下标index位置元素设为element |
| void clear( ) | 清空 |
| boolean contains(Object o) | 判断o是否在线性表中 |
| int indexOf(Object o) | 返回第一个o所在下标 |
| int lastIndexOf(Object o) | 返回最后一个o的下标 |
| List<E> subList(int fromIndex,int toIndex) | 截取部分list |
4.LinkedList的遍历
与顺序表ArrayList相同，LinkedList的遍历可以通过直接打印，for循环或for-each或迭代器(正向)实现，这里主要介绍使用反向迭代器(倒着打印)遍历LinkedList
import java.util.LinkedList;
import java.util.ListIterator;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
ListIterator<Integer> iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
System.out.println(iterator.previous());
}
}
}
5.ArrayList与LinkedList的区别
ArrayList
- 存储空间：物理上一定连续
- 随机访问：支持，时间复杂度为O(1)
- 头插：需要移动元素，效率低，时间复杂度为O(n)
- 插入：空间不够时需要扩容
- 应用场景：元素高效存储和频繁访问
LinkedList
- 存储空间：逻辑上连续，但物理上不一定连续
- 随机访问：不支持，时间复杂度为O(n)
- 头插：只需修改引用的指向，时间复杂度为O(1)
- 插入：没有容量的概念
- 应用场景：任意位置的频繁插入和删除