数据结构之链表（JAVA实现）| CSDN创作打卡
电子转码第一课。从链表开始吧
主要是集合了书本和网络上的各种学习资料，方便之后自己的复习和总结。资料附在文章后，如侵删。
目录
1. 什么是链表
2. 链表的实现原理
3. JAVA版自己动手写一个链表
1. 什么是链表
链表是一种物理结构上非顺序、非连续的存储结构，链表中数据元素的逻辑顺序是通过指针连接 次序来实现的。
每一个链表中都包含多个节点，每个节点又包含两部分，数据域（存储数据元素）和引用域（指向下一个节点或存储上一个节点信息）。
常用的单链表结构有以下几类：
1. 无头单向非循环链表
2. 带头双向循环链表
其中，无头单向非循环链表主要用作其他数据结构的子结构，一般不用于存储数据。在笔试面试中常见。
带头双向循环链表主要在实际工程中存储数据。
2. 链表的实现原理
一个链表节点类的实现包含两部分，数据和指向下一节点的指针（若为双向链表，还包含指向上一节点的指针）；
链表类需包含头节点、尾节点和链表大小，方法包含添加（插入）和删除等。
3. JAVA版自己动手写一个链表
JAVA中的实现原理就是链表。具体的操作方法可见Java集合用法总结 - 简书
以下为单向链表中的节点类及链表常用方法的JAVA实现。
节点类：
class ListNode{int val;ListNode next= null;ListNode(){ }ListNode(int val){this.val = val;}
}链表类：
class List {private ListNode head = null;//判断链表是否为空public boolean empty(ListNode head){if(head.next==null){return true;}return false;}//计算链表的长度public int size(){if(head==null){return 0;}int size = 1;ListNode tem = head;while(tem.next!=null){size++;tem = tem.next;}return size;}//在链表尾部添加元素public void add(int d){ListNode element = new ListNode(d);if(head == null){head = element;return;}ListNode tem = head;while(tem.next!= null){tem = tem.next;}tem.next = element;}//在第i个节点尾部添加元素d(第一个节点的index为1）public void addAtIndexI(int i, int d){if(i<1 || i>size()){return;}ListNode element = new ListNode(d);ListNode tem = head;while(i!=1){tem = tem.next;i--;}ListNode tem2 = tem.next;tem.next = element;element.next = tem2;}//删除第i个节点public boolean deleteNode(int i){if(i<1 || i>size()){return false;}if(i == 1){head = head.next;return true;}ListNode tem = head;while (i!=2){tem = tem.next;i--;}ListNode tem2 = tem.next.next;tem.next = tem2;return true;}//查找第i个节点的内容public int get(int i){if(i<1 || i>size()){return 0;}if(i==1){System.out.println(head.val);return head.val;}ListNode tem = head;while (i!=1){tem = tem.next;i--;}return tem.val;}//打印链表public void print(){int length = size();if(length==0){return;}ListNode tem = head;while (length!=0){System.out.print(tem.val+" ");tem = tem.next;length--;}System.out.println();}
}测试：
public class Main{public static void main(String[] args){List list = new List();list.add(1);list.add(2);list.add(3);list.add(4);System.out.println(list.size());list.print();list.deleteNode(2);list.print();System.out.println(list.get(3));list.addAtIndexI(2,5);list.print();}
}参考链接：
看完这篇文章还不会链表，请寄刀片给我 - 知乎
Java-链表（单向链表、双向链表） - 南孚先生 - 博客园
Java基础--单链表的实现_鱼非子-CSDN博客_java链表
链表的原理及java实现 - 刘凌枫羽 - 博客园
