由于数组是连续空间上存储的，因此，在数组的随机读取上可以直接读取，但是，若是在随机位置对元素进行增添与删除，那么需要移动大量的数据，因此有另外一种数据结构能弥补这种缺陷——链表
概念通过把数据存储在节点里，节点中存储下一个节点的地址，从而实现将每个节点串成串子。在物理结构上是非连续的，但是在逻辑层面上，我们认为链表是连续的。
结构链表具有多种结构
- 单向或双向
- 带头或不带头
- 循环或非循环
也即是说，一共有8种链表的结构，其中最经典的就是单向不带头非循环结构
MySingleLinkedListpublic class SingleLinkedList {
public static class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public ListNode head;
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
//尾插法
public void addLast(int data){
ListNode cur = head;
if(cur == null){
ListNode node = new ListNode(data);
head = node;
return;
}
while(cur.next != null){
cur = cur.next;
}
ListNode node = new ListNode(data);
cur.next = node;
}
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data){
if(index < 0 || index > size()){
return false;
}
if(index == 0){
addFirst(data);
return true;
}
if (index == size()){
addLast(data);
return true;
}
int x = 0;
ListNode cur = head;
while(cur.next != null && x != index){
cur = cur.next;
x++;
}
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
return true;
}
//查找是否包含关键字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){
if(head.val == key ){
head = head.next;
return;
}
ListNode cur = head;
while(cur.next != null){
if(cur.next.val == key){
cur.next = cur.next.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
while(head != null && head.val == key){
head = head.next;
}
if(head == null){
return;
}
ListNode cur = head.next;
ListNode prev = head;
while(cur != null){
if(cur.val == key){
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
}
//得到单链表的长度
public int size(){
int count = 0;
ListNode cur = head;
while(cur != null){
cur = cur.next;
count++;
}
return count;
}
public void display(){
ListNode cur = head;
while(cur != null){
System.out.println(cur.val);
cur = cur.next;
}
}
public void clear(){
ListNode cur = head;
ListNode prev = cur;
while(cur != null){
cur = cur.next;
prev = null;
prev = cur;
}
}
}
MyLinkedList
public class LinkedList {
public static class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next, ListNode prev) {
this.val = val;
this.next = next;
this.prev = prev;
}
}
public ListNode head;
public ListNode tail;
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.prev = null;
node.next = head;
head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
node.prev = tail;
node.next = null;
tail = node;
}
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data){
if(index < 0 || index > size()){
return false;
}
if(index == 0){
addFirst(data);
return true;
}
if (index == size()){
addLast(data);
return true;
}
int x = 0;
ListNode cur = head;
while(cur.next != null && x != index){
cur = cur.next;
x++;
}
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
return true;
}
//查找是否包含关键字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){
if(head.val == key ){
head = head.next;
return;
}
ListNode cur = head;
while(cur.next != null){
if(cur.next.val == key){
cur.next = cur.next.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
while(head != null && head.val == key){
head = head.next;
}
if(head == null){
return;
}
ListNode cur = head.next;
ListNode prev = head;
while(cur != null){
if(cur.val == key){
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
}
//得到单链表的长度
public int size(){
int count = 0;
ListNode cur = head;
while(cur != null){
cur = cur.next;
count++;
}
return count;
}
public void display(){
ListNode cur = head;
while(cur != null){
System.out.println(cur.val);
cur = cur.next;
}
}
public void clear(){
ListNode cur = head;
ListNode prev = cur;
while(cur != null){
cur = cur.next;
prev = null;
prev = cur;
}
}
LinkedList的使用
构造方法
| 方法 | 解释 |
|---|---|
| LinkedList() | 无参构造 |
| public LinkedList(Collection c) | 使用其他集合容器中元素构造List |
示例：
public static void main(String[] args) {
// 构造一个空的LinkedList
List list1 = new LinkedList<>();
List list2 = new ArrayList<>();
list2.add("1");
list2.add("2");
// 使用ArrayList构造LinkedList
List list3 = new LinkedList<>(list2);
}
其他方法
| 方法 | 解释 |
|---|---|
| boolean add(E e) | 尾插 e |
| void add(int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll(Collection 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 subList(int fromIndex, int toIndex) | 截取部分 list |
for (int e:list) {
System.out.print(e + " ");
}
迭代器
ListIterator反向迭代it = list.listIterator(); while(it.hasNext()){ System.out.print(it.next()+ " "); }
ListIteratorArrayList和LinkedList的区别rit = list.listIterator(list.size()); while (rit.hasPrevious()){ System.out.print(rit.previous() +" "); }
| 不同点 | ArrayList | LinkedList |
|---|---|---|
| 存储空间上 | 物理上连续 | 逻辑上连续，物理上不一定连续 |
| 随机访问 | 可 | 否 |
| 头插 | O(N) | O(1) |
| 容量 | 空间不够时扩容 | 没有容量的概念 |
| 应用 | 元素高效存储，频繁访问 | 频繁任意位置插入和删除 |
