电子转码第一课。从链表开始吧

主要是集合了书本和网络上的各种学习资料，方便之后自己的复习和总结。资料附在文章后，如侵删。

目录

1、什么是链表

2、链表的实现原理

3、JAVA版自己动手写一个链表

1、什么是链表

链表是一种物理结构上非顺序、非连续的存储结构，链表中数据元素的逻辑顺序是通过指针连接 次序来实现的。

每一个链表中都包含多个节点，每个节点又包含两部分，数据域（存储数据元素）和引用域（指向下一个节点或存储上一个节点信息）。

常用的单链表结构有以下几类：

1、无头单向非循环链表

2、带头双向循环链表

        

其中，无头单向非循环链表主要用作其他数据结构的子结构，一般不用于存储数据。在笔试面试中常见。

带头双向循环链表主要在实际工程中存储数据。

2、链表的实现原理

一个链表节点类的实现包含两部分，数据和指向下一节点的指针（若为双向链表，还包含指向上一节点的指针）；

链表类需包含头节点、尾节点和链表大小，方法包含添加（插入）和删除等。

3、JAVA版自己动手写一个链表

JAVA中linkedList的实现原理就是链表。具体的操作方法可见Java集合linkedList用法总结 - 简书

以下为单向链表中的节点类及链表常用方法的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实现 - 刘凌枫羽 - 博客园