链表

Linked List 有序

链表是以节点的方式来存储，链式存储每个节点包含 data 域， next 域：指向下一个节点链表的各个节点不一定是连续存放链表分带头节点的链表和没有头节点的链表，根据需求而定

单向链表

head 节点：不存放具体的数据；表示单链表头

添加（创建）

先创建一个 head 头节点，作用是表示单链表的头每添加一个节点，直接加入到链表的最后

遍历

通过一个辅助变量，帮助遍历列表

单向链表的创建，添加，遍历

class HeroNode{}: 定义变量，构造器，重写方法class SingleLinkedList{}: 定义添加节点的方法，以及显示链表的方法main方法中实例化 node，调用方法

package linkedlist;// single linked listpublic class Demo00 {public static void main(String[] args) {// test// create NodesHeroNode heroNode1 = new HeroNode(1, "batman", "bat");HeroNode heroNode2 = new HeroNode(2, "spiderman", "spider");HeroNode heroNode3 = new HeroNode(3, "american captain", "captain");HeroNode heroNode4 = new HeroNode(4, "hulk", "big green");// create linked listSingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add(heroNode1);singleLinkedList.add(heroNode2);singleLinkedList.add(heroNode3);singleLinkedList.add(heroNode4);singleLinkedList.showList();}}// define SingleLinkedList to manage herosclass SingleLinkedList{// initialize a head node, which cannot move and store empty valueprivate HeroNode head = new HeroNode(0,"","");// add node to single linked list// when number order is not considered,// find the last node of current linked list// make next pointer of the last node point to the new nodepublic void add(HeroNode heroNode){// a assistant variable is required, because head node cannot moveHeroNode temp = head;// traverse the linked list and last nodewhile(true){// read the last nodeif(temp.next == null){break;}// not reach the last node, move temp to next nodetemp = temp.next;}// temp points to the last node of linked list when drop out the loop// next of this node points to the new nodetemp.next = heroNode;}// show the listpublic void showList(){// determine if the linked list is emptyif(head.next == null){System.out.println("empty linked list");return;}// use a temp variable, due to unmovable headHeroNode temp = head.next;while(true){// determine if gets to the linked list's endif(temp == null){break;}// outputSystem.out.println(temp);// move temp to nexttemp = temp.next;}}}// define HeroNode, each HeroNode object is a Nodeclass HeroNode{public int id;public String name;public String nickname;public HeroNode next; // point to next Node// constructorpublic HeroNode(int id,String name,String nickname){this.id = id;this.name = name;this.nickname = nickname;}// for pretty print, override toString()@Overridepublic String toString() {return "HeroNode{" +"id=" + id +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}}

// outputHeroNode{id=1, name='batman', nickname='bat'}HeroNode{id=2, name='spiderman', nickname='spider'}HeroNode{id=3, name='american captain', nickname='captain'}HeroNode{id=4, name='hulk', nickname='big green'}

按照 id 进行添加

首先找到新添加的节点的位置，通过辅助指针找，遍历新的节点的 next = temp.nexttemp.next = 新的节点

新加入： addByOrder()

package linkedlist;// single linked listpublic class Demo00 {public static void main(String[] args) {// test// create NodesHeroNode heroNode1 = new HeroNode(1, "batman", "bat");HeroNode heroNode2 = new HeroNode(2, "spiderman", "spider");HeroNode heroNode3 = new HeroNode(3, "american captain", "captain");HeroNode heroNode4 = new HeroNode(4, "hulk", "big green");// create linkSingleLinkedList singleLinkedList = new SingleLinkedList();// singleLinkedList.add(heroNode1);// singleLinkedList.add(heroNode2);// singleLinkedList.add(heroNode3);// singleLinkedList.add(heroNode4);// singleLinkedList.showList();singleLinkedList.addByOrder(heroNode3);singleLinkedList.addByOrder(heroNode2);singleLinkedList.addByOrder(heroNode1);singleLinkedList.addByOrder(heroNode4);singleLinkedList.showList();}}// define SingleLinkedList to manage herosclass SingleLinkedList{// initialize a head node, which cannot move and store empty valueprivate HeroNode head = new HeroNode(0,"","");// add node to single linked list// when number order is not considered,// find the last node of current linked list// make next pointer of the last node point to the new nodepublic void add(HeroNode heroNode){// a assistant variable is required, because head node cannot moveHeroNode temp = head;// traverse the linked list and last nodewhile(true){// read the last nodeif(temp.next == null){break;}// not reach the last node, move temp to next nodetemp = temp.next;}// temp points to the last node of linked list when drop out the loop// next of this node points to the new nodetemp.next = heroNode;}// add node according to idpublic void addByOrder(HeroNode heroNode){// use temp pointer to find the location where should add// the temp we find is the previous node of target locationHeroNode temp = head;boolean flag = false; // flag if the id exists, false is the default valuewhile(true){if(temp.next == null){break;}if(temp.next.id>heroNode.id){// find the location, it is behind tempbreak;}else if(temp.next.id == heroNode.id){// the heroNode waiting for insert already in the listflag = true;}temp = temp.next; // move back, traverse current linked list}// judgement flag's valueif(flag){// cannot insert, id already exists;System.out.printf("id %d waiting for insertion already exists\n",heroNode.id);}else{// insert to next position of tempheroNode.next = temp.next;temp.next = heroNode;}}// show the listpublic void showList(){// determine if the linked list is emptyif(head.next == null){System.out.println("empty linked list");return;}// use a temp variable, due to unmovable headHeroNode temp = head.next;while(true){// determine if gets to the linked list's endif(temp == null){break;}// outputSystem.out.println(temp);// move temp to nexttemp = temp.next;}}}// define HeroNode, each HeroNode object is a Nodeclass HeroNode{public int id;public String name;public String nickname;public HeroNode next; // point to next Node// constructorpublic HeroNode(int id,String name,String nickname){this.id = id;this.name = name;this.nickname = nickname;}// for pretty print, override toString()@Overridepublic String toString() {return "HeroNode{" +"id=" + id +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}}

单链表的修改

Update()

package linkedlist;// update info// single linked listpublic class Demo01 {public static void main(String[] args) {// test// create NodesHeroNode heroNode1 = new HeroNode(1, "batman", "bat");HeroNode heroNode2 = new HeroNode(2, "spiderman", "spider");HeroNode heroNode3 = new HeroNode(3, "american captain", "captain");HeroNode heroNode4 = new HeroNode(4, "hulk", "big green");// create linkSingleLinkedList singleLinkedList = new SingleLinkedList();// singleLinkedList.add(heroNode1);// singleLinkedList.add(heroNode2);// singleLinkedList.add(heroNode3);// singleLinkedList.add(heroNode4);// singleLinkedList.showList();// add by ordersingleLinkedList.addByOrder(heroNode3);singleLinkedList.addByOrder(heroNode2);singleLinkedList.addByOrder(heroNode1);singleLinkedList.addByOrder(heroNode4);singleLinkedList.showList();// update node infoHeroNode newHeroNode = new HeroNode(2,"wonder woman","baby");singleLinkedList.update(newHeroNode);System.out.println("linked list after update");singleLinkedList.showList();}}// define SingleLinkedList to manage herosclass SingleLinkedList{// initialize a head node, which cannot move and store empty valueprivate HeroNode head = new HeroNode(0,"","");// add node to single linked list// when number order is not considered,// find the last node of current linked list// make next pointer of the last node point to the new nodepublic void add(HeroNode heroNode){// a assistant variable is required, because head node cannot moveHeroNode temp = head;// traverse the linked list and last nodewhile(true){// read the last nodeif(temp.next == null){break;}// not reach the last node, move temp to next nodetemp = temp.next;}// temp points to the last node of linked list when drop out the loop// next of this node points to the new nodetemp.next = heroNode;}// add node according to idpublic void addByOrder(HeroNode heroNode){// use temp pointer to find the location where should add// the temp we find is the previous node of target locationHeroNode temp = head;boolean flag = false; // flag if the id exists, false is the default valuewhile(true){if(temp.next == null){break;}if(temp.next.id>heroNode.id){// find the location, it is behind tempbreak;}else if(temp.next.id == heroNode.id){// the heroNode waiting for insert already in the listflag = true;}temp = temp.next; // move back, traverse current linked list}// judgement flag's valueif(flag){// cannot insert, id already exists;System.out.printf("id %d waiting for insertion already exists\n",heroNode.id);}else{// insert to next position of tempheroNode.next = temp.next;temp.next = heroNode;}}// update node information according to id, and id is uneditable// update according to the id of newHeroNodepublic void update(HeroNode newHeroNode){// determine if it is emptyif(head.next==null){System.out.println("linked list empty");return;}// find the node need to edit, according to id// define an assistant variableHeroNode temp = head.next;boolean flag = false; // whether find the nodewhile(true){if(temp==null){break; // already traverse done the linked list}if(temp.id==newHeroNode.id){// get it!flag = true;break;}temp = temp.next;}// determine whether find the id need to be changed, according to flagif(flag){temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;}else{// not find itSystem.out.printf("id %d is not find, cannot update\n",newHeroNode);}}// show the listpublic void showList(){// determine if the linked list is emptyif(head.next == null){System.out.println("empty linked list");return;}// use a temp variable, due to unmovable headHeroNode temp = head.next;while(true){// determine if gets to the linked list's endif(temp == null){break;}// outputSystem.out.println(temp);// move temp to nexttemp = temp.next;}}}// define HeroNode, each HeroNode object is a Nodeclass HeroNode{public int id;public String name;public String nickname;public HeroNode next; // point to next Node// constructorpublic HeroNode(int id,String name,String nickname){this.id = id;this.name = name;this.nickname = nickname;}// for pretty print, override toString()@Overridepublic String toString() {return "HeroNode{" +"id=" + id +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}}

单链表的删除

先要找到需要删除的这个节点的前一个节点 tempTemp.next = temp.next.next (跳过需要删除的节点，进行连接)被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

// delete nodepublic void deleteNode(int id) {// need a temp node to find the front node of the node waiting for deleting// temp.next.id compares with node.id(should be deleted)HeroNode temp = head;boolean flag = false; // whether find the previous node of the node be deletedwhile (true) {if (temp.next == null) {// to the end of linked listbreak;}if (temp.next.id == id) {// find itflag = true;break;}temp = temp.next;// traversal}// judge flagif (flag) {// find// deletetemp.next = temp.next.next;} else {System.out.printf("要删除的 %d 节点不存在", id);}}

单链表练习题

求单链表中有效节点的个数

// delete nodepublic void deleteNode(int id) {// need a temp node to find the front node of the node waiting for deleting// temp.next.id compares with node.id(should be deleted)HeroNode temp = head;boolean flag = false; // whether find the previous node of the node be deletedwhile (true) {if (temp.next == null) {// to the end of linked listbreak;}if (temp.next.id == id) {// find itflag = true;break;}temp = temp.next;// traversal}// judge flagif (flag) {// find// deletetemp.next = temp.next.next;} else {System.out.printf("要删除的 %d 节点不存在", id);}}

查看单链表中的倒数第k个节点

create a method getting the head node and an indexindex refers to index-last nodetraversel linked list from head to end, get the length of the linked listTraverse linked list to (size-index)if find, return node, else, return null

package linkedlist;import linkedlist.Demo02;public class Demo03 {// show the k-last nodepublic static HeroNode findLastKNode(HeroNode head,int index){// if linked list empty, return nullif(head.next==null){return null;}// get lengthint size = Demo02.getLength(head);// size - index : target : k-last// check indexif(index <= 0 || index > size){return null;}// define auxiliary variable, for loop to k-lastHeroNode temp = head.next;for (int i = 0; i < size-index; i++) {temp = temp.next;}return temp;}}

测试在Demo01中

单链表的反转

define a node: reverseHead = new HeroNode();traverse original linked list from head to end, get each node and put into forefront of the new linked listoriginal linked list - head.next = reverseHead.next

package linkedlist;// reverse single linked listpublic class Demo04 {public static void reverse(HeroNode head){// if linked list is empty, return directlyif(head.next == null||head.next.next==null){return;}// define an auxiliary pointer, helping traverse original listHeroNode cur = head.next;HeroNode next = null; // point next node of current nodeHeroNode reverseHead = new HeroNode(0,"","");// traverse original list from head to end// pick each node and put into forefront of reverseHeadwhile(cur!=null){next = cur.next; // store next node of current nodecur.next = reverseHead.next; // put next node of current node to forehead of new listreverseHead.next = cur; // cur connect to new listcur = next; // move back cur}// head.next --> reverseHead.nexthead.next = reverseHead.next;}}

从尾到头打印单链表

反转单链表，遍历打印 （问题：破坏了原有链表的结构），不建议这样做可以利用 stack 数据结构，将各个节点压入栈中，利用栈先进后出的特点，实现逆序打印

栈的使用

package linkedlist;import java.util.Stack;// use of stackpublic class Demo05 {public static void main(String[] args) {Stack<String> stack = new Stack<>();// instack.add("jack");stack.add("tom");stack.add("smith");// outwhile(stack.size()>0){System.out.println(stack.pop()); // pop the top data of the stack}}}

package linkedlist;import java.util.Stack;// reverse print linked list using stackpublic class Demo06 {public static void reversePrint(HeroNode head){if(head.next==null){return; // empty linked list}// create stack and get node inStack<HeroNode> stack = new Stack<>();HeroNode cur = head.next;// put all nodes of linked list into stackwhile(cur!=null){stack.push(cur);cur = cur.next; // move back cur}// print node in stackwhile(stack.size()>0){System.out.println(stack.pop());// first in, end out}}}