一. LinkedList简介
LinkedList和ArrayList一样, 在集合框架中, LInkedList也是一个类, 实现了List接口:
【说明】 1. LinkedList实现了List接口 2. LinkedList的底层使用了双向链表 3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问 4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1) 5. LinkedList比较适合任意位置插入的场景
但是与我们上次定义的MySingleList不同, 上次的定义的无头单向非循环链表, 而LinkedLIst是无头双向非循环链表, 画图理解一下:
二.LinkedList的简单实现
无头双向非循环链表的实现:
IList.java:
public interface IList {//头插法 void addFirst(int data);//尾插法 void addLast(int data);//任意位置插入,第一个数据节点为0号下标 void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中 boolean contains(int key);//删除第一次出现关键字为key的节点 void remove(int key);//删除所有值为key的节点 void removeAllKey(int key);//得到单链表的长度 int size(); void clear() ; void display() ;}IndexException.java:
public class IndexException extends RuntimeException{public IndexException() {}public IndexException(String message) {super(message);}}KeyException.java:
public class KeyException extends RuntimeException{public KeyException() {}public KeyException(String message) {super(message);}}MyLinkedList.java:
/** * Created with IntelliJ IDEA. * Description: * User: Jiang Jinxi * Date: 2023-12-27 * Time: 13:42 */public class MyLinkedList implements IList {static class ListNode{public ListNode prev;public int val;publicListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;@Overridepublic 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;}}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else{last.next = node;node.prev = last;last = node;}}@Overridepublic void addIndex(int index, int data) {if(index size()){throw new IndexException("index 不合法" + index);}if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}ListNode cur = head;while(index != 0){cur = cur.next;index--;}//插入结点 ListNode node = new ListNode(data);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}@Overridepublic boolean contains(int key) {ListNode cur = head;while(cur!=null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(!contains(key)){throw new KeyException("找不到key" + key);}//如果只有一个结点且该节点的值就是我要删的数字 if(head.next == null && head.val == key){head = null;last = null;return;}//循环遍历结点ListNode cur = head;while(cur!=null) {if (cur.val == key) {//如果要删除的是头结点if(cur == head){head = head.next;head.prev = null;return;}//如果要删除的是尾结点if(cur == last){last = last.prev;last.next = null;return;}//是中间结点cur.prev.next = cur.next;cur.next.prev = cur.prev;return;}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {if(!contains(key)){throw new KeyException("找不到key" + key);}ListNode cur = head;if(cur.next == null && cur.val == key){head = null;last = null;return;}while(cur!=null) {if (cur.val == key) {if(cur == head){head = head.next;head.prev = null;}if(cur == last) {last = last.prev;last.next = null;}cur.prev.next = cur.next;cur.next.prev = cur.prev;}cur = cur.next;}}@Overridepublic int size() {ListNode cur = head;int count = 0;while(cur != null){cur = cur.next;count++;}return count;}@Overridepublic void clear() {head = null;last = null;}@Overridepublic void display(){ListNode cur = head;while(cur != null) {System.out.println(cur.val + " ");cur = cur.next;//遍历所有节点}}}三. LinkedList的使用
1. LinkList的构造
1)无参构造
// 构造一个空的 LinkedList List < Integer > list1 = new LinkedList ();
2)使用其他集合容器中元素构造List
List < String > list2 = new ArrayList (); list2 . add ( “JavaSE” ); list2 . add ( “JavaWeb” ); list2 . add ( “JavaEE” ); // 使用 ArrayList 构造 LinkedList List < String > list3 = new LinkedList ( list2 );
2. LinkedList的其他常用方法介绍
方法与ArrayList类似, 不再赘述
3. LinkedList的遍历
第一种:for循环
// 使用下标+for遍历
for (int i = 0; i < linkedList.size(); i++) {
System.out.print(linkedList.get(i) + ” “);
}
第二种: for-each
// 借助foreach遍历
for (Integer x: linkedList) {
System.out.print(x+ ” “);
}
System.out.println();
第三种: 使用迭代器
可以使用迭代器的原因是: 继承了Iterable接口
从前往后:
Iterator it = linkedList.iterator();
while(it.hasNext()){
System.out.print(it.next() + ” “);
}
或
ListIterator it = linkedList.listIterator();
while(it.hasNext()){
System.out.print(it.next() + ” “);
}
注: ListIterator是Iterator的子类
从后往前:
ListIterator it = linkedList.listIterator(linkedList.size() );
while(it.hasPrevious()){
System.out.print(it.previous() + ” “);
}
四. ArrayList和LinkedList的区别
