杨邦胜酒店设计公司官网_上海网站建设哪家快速上线_百度快速排名优化工具_经典软文文案

文章目录

一、ArrayList的缺陷
二、链表
- 1.链表的概念及结构
- 2.链表的实现
总结

一、ArrayList的缺陷

在前一章博客中我们以及熟悉了ArrayList的使用，并且对其部分方法进行了自我实现，当我们探究其源码时会发现，ArrayList底层使用数组来储存元素：

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{// ...
// 默认容量是10private static final int DEFAULT_CAPACITY = 10;//...
// 数组：用来存储元素transient Object[] elementData; // non-private to simplify nested class access// 有效元素个数private int size;public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}//....
}

由于其底层 “数组” 是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构。

二、链表

1.链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。正如我们喜欢的托马斯小火车：

但在实际情况中链表的结构多重多样，以下是其8种链表组合：

1.单向或者双向：

2.带头或者不带头：

3.循环或者非循环：

以上三组结构能够组成八种不同的不同的链表结构，但不要慌！我们主要了解以下两种结构：

$\bullet$ 无头单向非循环链表：

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
$\bullet$ 无头双向链表：

在Java的集合框架库中LinkedList底层实现就是无头双向循环链表.

2.无头单项非循环链表的实现

 //头插法public void addFirst(int data);
//尾插法public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中public boolean contains(int key);
//删除第一次出现关键字为key的节点public void remove(int key);
//删除所有值为key的节点public void removeAllKey(int key);
//得到单链表的长度public int size();
//清空链表public void clear();
//打印链表public void display();

我们依次实现上述方法，首先我们创建一个内部类，原因及代码如下：

public class LinkedList implements IList{public class ListNode{private int val;private ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;
}

那么我们就依次实现：(在实现过程我就不多一一讲解了)

2.1 addFirst(int data)

 public void addFirst(int data) {ListNode del=new ListNode(data);del.next=head;head=del;}

2.2 size()

public int size() {int len=0;ListNode cur=head;while(cur!=null){cur=cur.next;len++;}return len;}

2.3 display()

public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}}

2.4 addLast(int data)

public void addLast(int data) {ListNode del=new ListNode(data);if(head==null){head=del;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=del;}

2.5 addIndex(int index, int data)

private void checkindex(int index) throws PosIllegal{int len=size();if(index<0||index>len){throw new PosIllegal("index位置不合法！！！");}}@Overridepublic void addIndex(int index, int data) {int len=size();try{checkindex(index);ListNode cur=head;ListNode del=new ListNode(data);if(index==0){addFirst(data);return;}else if (index==len){addLast(data);return;}else{for (int i = 1; i <len ; i++) {if (i == index) {del.next=cur.next;cur.next=del;}cur=cur.next;}}}catch(PosIllegal e){e.printStackTrace();System.out.println("index的位置不合法！！！");}}

异常的实现可以查阅：代码如下：

2.6 contains(int key)

public boolean contains(int key) {ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}

2.7 remove(int key)

public void remove(int key) {if(head==null){return;}ListNode cur=head;while(cur.next!=null) {if(head.val==key){head=head.next;return;}if(cur.next.next==null&&cur.next.val==key){cur.next=null;return;}if (cur.next.val == key) {ListNode del = cur.next;cur.next = del.next;}cur = cur.next;}return;}

2.8 removeAllKey(int key)

public void removeAllKey(int key) {ListNode cur=head;ListNode pre=head;if(head==null){return;}while(cur!=null){if(cur.val==key){pre.next=cur.next;cur=cur.next;}else{pre=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}

作业

1. 反转一个单链表 https://leetcode-cn.com/problems/reverse-linked-list/description/https://leetcode-cn.com/problems/reverse-linked-list/description/

2. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点 https://leetcode-cn.com/problems/middle-of-the-linked-list/description/https://leetcode-cn.com/problems/middle-of-the-linked-list/description/

3. 链表的回文结构 https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-rankinghttps://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking 下一篇我们将给出上述三个题目的解题思路，另外将介绍双向链表，以及对其进行简单实现！