长春经开人才网_硬件开发需求_国外域名注册网站_123网址之家

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)
• 插入：没有容量的概念
• 应用场景：任意位置的频繁插入和删除