链表是一种常见的数据结构，链表由一系列的节点组成，这个节点就是链接点，每个链接点由两部分组成：数据域和指针域。使用链表结构可以克服数组结构需要事先知道数据大小的缺点，并且链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了随机读取数组的优势，同时链表由于增加了节点的指针字段，空间开销也比较大。对链表更好的理解是：把链表想象成一列火车，每一节车厢都是相互连接的。只要找到机车，就能找到具体的车体。链表也是一样，我们只关心它的头部。1.单向链表1.1单向链表示意图单向链表的一个链接点包含一个数据字段和一个指向下一个链接点的指针。头节点还包括数据域和指针域，但一般为了查找方便，头节点不写数据，最后一个节点的指针指向null。1.2实现单向链表的存储等操作创建一个链接点的实体类publicclassNode{//数据域publiclongdata;//指针域publicNodeext;publicNode(longvalue){this.data=value;}}1.2.1插入节点在头节点后插入节点，第一步需要将新插入的节点指向头节点指向的节点，而第二步是将头节点指向新插入的节点。插入一个节点只需要改变一个引用，所以复杂度是O(1)。publicclassLinkList{privateNodehead;/***在头节点之后插入一个节点*/publicvoidinsertFirst(longvalue){Nodenode=newNode(value);node.next=head;head=node;}}1.2.2删除一个节点之后头节点节点删除头节点之后的一个节点，也就是说头节点指向这个节点的下一个节点。复杂度也是O(1)。publicNodeleteFirst(){Nodetmp=head;head=tmp.next;returntmp;}1.2.3根据数据字段查找节点Search需要比较每个节点的数据。理论上，平均需要N/2次才能找到一个节点。所以复杂度是O(N)。publicNodefind(longvalue){Nodecurrent=head;while(current.data!=value){if(current.next==null){returnnull;}current=current.next;}returncurrent;}1.2.4根据数据和删除结果点搜索需要比较每个节点的数据。理论上删除一个节点平均需要N/2次，所以复杂度为O(N)。publicNodelete(intvalue){Nodecurrent=head;//当前节点的前一个节点Nodepre=head;while(current.data!=value){if(current.next==null){returnnull;}pre=current;current=current.next;}if(current==head){head=head.next;}else{pre.next=current.next;}returncurrent;}两个双端链表2.1双端链表示意图list双端链表是在单链表的基础上，头节点增加了对尾节点的引用。2.2实现双端链表存储等操作2.2.1从头插入节点如果链表为空，则设置尾节点为新加入的节点。复杂度为O(1)。publicclassFirstLastLinkList{privateNodefirst;privateNodelast;/***在头节点后插入一个节点*/publicvoidinsertFirst(longvalue){Nodenode=newNode(value);if(first==null){last=node;}node.next=first;first=node;}}2.2.2从尾部插入一个节点如果链表为空，则设置头节点为新增节点，否则设置尾节点之后的节点为新增节点。复杂度为O(1)。publicvoidinsertLast(longvalue){Nodenode=newNode(value);if(first==null){first=node;}else{last.next=node;}last=node;}2.2.3从头部删除判断head该点是否有下一个节点，如果没有，则将结束节点设置为null，复杂度为O(1)。publicNodeleteFirst(){Nodetmp=first;if(first.next==null){last=null;}first=tmp.next;returntmp;}三个双向链表除了节点的引用，还保存了引用到上一个节点。3.2实现双向链表存储等操作链接节点实体类publicclassNode{//数据域publiclongdata;//下一个节点指针域publicNodeext;//上一个节点指针域publicNodeprev;publicNode(longvalue){this.data=value;}}3.2.1从头插入节点如果链表为空，则设置尾节点为新加入的节点，如果不为空，还需要将头节点的前一个节点设置为新添加的节点Node。插入一个节点只需要改变两个节点的引用，所以复杂度是O(1)。publicclassDoubleLinkList{privateNodefirst;privateNodelast;/***在头节点后插入一个节点*/publicvoidinsertFirst(longvalue){Nodenode=newNode(value);if(first==null){last=node;}else{first.prev=node;}node.next=first;first=node;}}3.2.2从尾部插入一个节点如果链表为空，则设置头节点为新加入的节点，否则设置尾节点的最后一个节点重点是新添加的节点。同时将新增节点的前一个节点设置为结束节点。插入一个节点只需要改变1个节点的引用，所以复杂度是O(1)。publicvoidinsertLast(longvalue){Nodenode=newNode(value);if(first==null){first=node;}else{last.next=node;node.prev=last;}last=node;}3.2.3来自scratch删除所有节点，判断头节点是否有下一个节点，如果没有，设置尾节点为null，否则设置头节点的下一个节点的prev为null。复杂度也是O(1)。publicNodeleteFirst(){Nodetmp=first;if(first.next==null){last=null;}else{first.next.prev=null;}first=tmp.next;returntmp;}3.2.4从节点中删除节点end如果头节点之后没有其他节点，则将头节点设置为null，否则将尾节点的前一个节点的下一个节点设置为null，将尾节点设置为前一个节点。复杂度为O(1)。publicNodeleteLast(){Nodetmp=last;if(first.next==null){first=null;}else{last.prev.next=null;}last=last.prev;returnlast;}四个摘要列表包含一个headerPoint和多个节点，头节点包含一个引用，通常称为first，它指向链表的第一个链接点。如果该节点的next为null，则表示该节点为结束节点。与数组相比，链表更适合插入和删除操作，而查找操作更复杂。还有一个好处就是链表不需要初始化内存大小，不会造成内存溢出（数组中插入元素的个数超过数组长度）或者内存浪费（数组声明的长度更长）比实际元素）。本文转载自微信公众号“Java之旅”，可通过以下二维码关注。转载本文请联系Java之旅公众号。
