目录

链表（线性表的链式存储）

代码实例：（链表构建，头插+尾插）

LinkedList

LinkedList的使用：

1、构造方法

 2、操作方法

LinkedList 和 ArrayList 的区别

链表（线性表的链式存储）

它可以不断扩容，无固定长度

每一个节点都是由value和next构成

有两种插入的方式：头插法尾插法

代码实例：（链表构建，头插+尾插）

public class Listnode {     public int value;     public Listnode next; //指针     public Listnode(int n) {         this.value=n;     }

public class Linklist {     //定义头指针     Listnode head;      //头插法     public void startAdd(int n) {         Listnode listnode=new Listnode(n);         listnode.next=head;//新节点的next是原来的首节点         head=listnode;//头结点指向新节点实现头插法     }     //尾插法     public void endAdd(int n) {         Listnode listnode=new Listnode(n);         //判断头结点是否为空，空就通过值传递把新节点传给头节点         if(head==null) {             head=listnode;             return;         }         //头结点不是空，则往下遍历，一直找到尾结点，此时temp就指向尾结点         Listnode temp=head;         while(temp.next!=null) {             temp=temp.next;         }         //尾结点的后面插入新节点         temp.next=listnode;     }      //把添加的值打印的方法     public void printLink() {         Listnode temp=head;         while(temp!=null) {             System.out.print(temp.value+"->");             temp=temp.next;         }     } }

测试类：

public class Test {     public static void main(String[] args) {         Linklist linklist=new Linklist();         linklist.endAdd(1);         linklist.endAdd(2);         linklist.startAdd(0);         linklist.startAdd(-1);         linklist.startAdd(-2);         linklist.printLink();     } }

LinkedList

在Java中，LinkedList（链表）是Java提供的一个实现了List接口的类。是基于双向链表结构实现的

LinkedList的使用：

1、构造方法

1、LinkedList()：创建一个空的LinkedList对象。

LinkedList list = new LinkedList<>(); 

2、LinkedList(Collection c)：创建一个包含指定集合中的元素的LinkedList对象。集合中的元素将按照迭代器返回的顺序添加到LinkedList中。

List collection = new ArrayList<>(); collection.add("Element 1"); collection.add("Element 2"); LinkedList list = new LinkedList<>(collection); 

3、LinkedList(LinkedList c)：创建一个包含指定LinkedList中的元素的LinkedList对象。指定LinkedList中的元素将按照迭代器返回的顺序添加到新的LinkedList中。

LinkedList originalList = new LinkedList<>(); originalList.add("Element 1"); originalList.add("Element 2"); LinkedList newList = new LinkedList<>(originalList); 

 2、操作方法

1、添加元素：

• add(E element)：在链表末尾添加一个元素。
• addFirst(E element)：在链表开头添加一个元素。
• addLast(E element)：在链表末尾添加一个元素。

LinkedList list = new LinkedList<>(); list.add("Element 1"); list.addFirst("Element 0"); list.addLast("Element 2"); 

2、获取元素：

• get(int index)：获取指定位置的元素。
• getFirst()：获取链表的第一个元素。
• getLast()：获取链表的最后一个元素。

LinkedList list = new LinkedList<>(); list.add("Element 1"); list.add("Element 2"); String element = list.get(0); String firstElement = list.getFirst(); String lastElement = list.getLast(); 

3、删除元素：

• remove(int index)：删除指定位置的元素。
• removeFirst()：删除链表的第一个元素。
• removeLast()：删除链表的最后一个元素。

LinkedList list = new LinkedList<>(); list.add("Element 1"); list.add("Element 2"); list.remove(0); list.removeFirst(); list.removeLast(); 

4、判断元素是否存在：

• contains(Object element)：检查链表是否包含指定元素。

LinkedList list = new LinkedList<>(); list.add("Element 1"); list.add("Element 2"); boolean containsElement = list.contains("Element 1"); 

5、获取链表大小和清空链表：

• size()：获取链表中元素的个数。
• isEmpty()：检查链表是否为空。
• clear()：清空链表中的所有元素。

LinkedList list = new LinkedList<>(); list.add("Element 1"); list.add("Element 2"); int size = list.size(); boolean isEmpty = list.isEmpty(); list.clear(); 

链表的优点：可以高效地插入和删除节点，而无需移动其他节点。

缺点：访问特定位置的节点需要从头部开始遍历，随机访问的效率较低。

LinkedList 和 ArrayList 的区别

首先说说动态数组ArrayList：

这是一个集合类型，在其内部维护了一个数组，可以自动调整其大小以容纳更多的元素。当你向这些集合中添加元素时，如果内部数组已满，它们会自动创建一个更大的新数组（扩容），并将旧数组的元素以及新元素复制到新数组中。

内部数组初始容量：10

触发扩容的条件：原有数组elementData满了之后就会扩容

扩容方式：新容量=原容量+(原容量>>1)

数组优点：可以随机访问，效率极高；缺点：需要连续的空间，而链表结构可以比较好的利用碎片化空间

LinkedList 和 ArrayList 的区别：

底层数据结构：LinkedList底层基于链表实现，而ArrayList底层基于动态数组实现。

插入和删除操作：由于LinkedList是基于链表的数据结构，插入和删除元素的操作比较高效，时间复杂度为O(1)，因为只需要调整节点的指针。而ArrayList的底层是动态数组，插入和删除操作需要移动其他元素，时间复杂度为O(n)，其中n是元素的数量。

随机访问：ArrayList支持高效的随机访问，可以通过索引快速获取元素，时间复杂度为O(1)。而LinkedList需要从头开始遍历链表才能找到指定位置的元素，时间复杂度为O(n)，其中n是索引位置。

内存消耗：由于LinkedList需要额外的指针来维护节点之间的连接关系，因此在存储相同数量的元素时，LinkedList通常会占用更多的内存空间。而ArrayList只需要连续的内存空间来存储元素。

迭代器性能：对于迭代器遍历操作，LinkedList的性能较好，因为只需要遍历链表中的节点即可。而ArrayList在使用迭代器遍历时，由于底层是数组，可能会导致性能稍差。