1.ArrayList的缺点
上篇文章我们已经对顺序表进行了实现,并且对ArrayList进行了使用,我们知道ArrayList底层是使用数组实现的.
由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。
2.链表
2.1 链表的概念与结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的.就像一列动车一样.
通过上图我们可以看到,一个链表中有一节一节的"车厢",还有中间的"链条".我们称每一节"车厢"为结点,我们可以看到每一个结点中有下一个结点的地址,链表就是通过存储节点的地址来连接起来的,还有该结点的值.上面就是我们需要重点掌握的一种链表类型,叫做单向无头非循环链表.其实链表还有好多类型,下面我们来展示.
2.2 链表的类型
链表有以下几种性质:有头/无头,单向/双向,循环/非循环
- 有头/无头
它们的区别就是,有头链表的head永远指向一个固定的结点,而无头链表的head永远在改变. - 单向/双向
3. 循环/非循环
上面几种性质排列组合可以得到许多中链表的类型,这里我们重点掌握2中即可,一种是单向无头非循环,它在笔面试中经常出现,另一种是是无头双向循环链表,Java中的LinkedList底层就是通过它来实现的.
3. 单向无头非循环链表实现
下面是要实现的接口,即链表中的常用方法:
public interface ILinkedList {
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();
}
下面我们来实现这些方法:
public class MyLinkedList implements ILinkedList {
static class Node{
public int val;
public Node next = null;
public Node(int val) {
this.val = val;
}
}
public Node head = null;
/**
* 创建默认链表
*/
public void createDeafultLinkedList(){
Node node = new Node(23);
this.head = node;
Node node1 = new Node(34);
node.next = node1;
Node node2 = new Node(45);
node1.next = node2;
Node node3 = new Node(56);
node2.next = node3;
Node node4 = new Node(67);
node3.next = node4;
}
/**
* 在链表头部添加新的结点
* @param data
*/
@Override
public void addFirst(int data) {
Node node = new Node(data);
// if(head == null){
// head = node;
// }else {
// node.next = head;
// head = node;
// }
//上面的代码其实没必要验证链表是否为空,head为null赋值过去还是null
node.next = this.head;
this.head = node;
}
/**
* 在尾部添加新的结点
* @param data
*/
@Override
public void addLast(int data) {
Node node = new Node(data);
Node cur = this.head;
if (this.head == null){
this.head = node;
}else {
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}
}
/**
* 在指定位置添加结点
* @param index
* @param data
*/
@Override
public void addIndex(int index, int data) {
if (index > size() || index < 0){
throw new IndexExeption("下标有误");
}
Node node = new Node(data);
if (this.head == null){
this.head = node;
return;//记得返回,不然会执行中间插入的代码
}
if (index == 0){//在链表头添加
addFirst(node.val);
return;
}
if (index == size()){//在链表尾部添加
addLast(node.val);
return;
}
//在中部添加
Node cur = this.head;
int count = 0;
while (count != index-1){//寻找cur的前一个结点
cur = cur.next;
count++;
}
node.next = cur.next;
cur.next = node;
}
/**
* 检测链表中是否含有指定的值
* @param key
* @return
*/
@Override
public boolean contains(int key) {
Node cur = this.head;
while (cur != null){//先遍历链表
if(cur.val == key){//在遍历的过程中如果等于,返回true
return true;
}
cur = cur.next;
}
return false;
}
/**
* 移除遇到的第一个值为key的元素
* @param key
*/
@Override
public void remove(int key) {
if (this.head == null){
return;
}
if (head.val == key){
head = head.next;
return;
}
Node cur = findPreNode(key);//需要找到前一个结点才可以删除
if (cur == null){//没找到要删除的结点
return;
}
cur.next = cur.next.next;
}
private Node findPreNode(int key){//找到要删除结点的前一个结点
Node cur = this.head;
while (cur.next != null){//这里必须写成next不等于null,否则下面可能会出现空指针异常
if (cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}
/**
* 移除所有符合值为key的结点
* @param key
*/
@Override
public void removeAllKey(int key) {
if (this.head == null){
return;
}
Node pre = this.head;
Node cur = this.head.next;
//先不要管头结点,先删中间的
while(cur != null){
if (cur.val == key){
pre.next = cur.next;
}else {
pre = pre.next;//若该结点不是要删除的结点,pre往后走
}
cur = cur.next;
}
//所有的都删完了,删除头结点
if (head.val == key){
head = head.next;
}
}
/**
* 计算链表大小
* @return
*/
@Override
public int size() {
int count = 0;
Node cur = this.head;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}
/**
* 清空链表
*/
@Override
public void clear() {
head = null;//为被引用的结点会被JWM回收
}
/**
* 打印链表
*/
@Override
public void display() {
Node cur = this.head;
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
/**
* 从指定位置开始打印链表
* @param node
*/
public void display(Node node) {
Node cur = node;
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
}
上面有几个问题需要注意
- 在中间插入元素的时候先要进行后链接,在进行前链接,如果先进行前链接,cur的下一个结点的地址就会丢失
- 在删除所有值为key的结点的时候,先删除head后符合条件的结点最后再处理head.
下面是对上述问题的动态演示:
[插入结点错误演示]
插入中间节点(错误)
[插入结点正确演示]
插入中间结点(正确)
[删除所有key结点]
删除所有key结点
下面我们对上述实现的方法进行测试:
**
* 开始测试
*/
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createDeafultLinkedList();
myLinkedList.addFirst(11);
myLinkedList.addLast(88);
myLinkedList.display();
System.out.println(myLinkedList.size());
myLinkedList.addIndex(2,33);
myLinkedList.display();
System.out.println(myLinkedList.contains(11));
System.out.println(myLinkedList.contains(12));
myLinkedList.addIndex(1,23);
myLinkedList.addIndex(1,23);
myLinkedList.addIndex(1,23);
myLinkedList.display();
myLinkedList.remove(23);
myLinkedList.display();
myLinkedList.removeAllKey(23);
myLinkedList.display();
myLinkedList.clear();
myLinkedList.display();
}
}
测试结果:
