Shulou(Shulou.com)06/03 Report--

This article will explain in detail how to use a single linked list in Java programming. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have some understanding of the relevant knowledge after reading this article.

Basic introduction

A linked list is an ordered list, but it is stored in memory as follows

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Linked lists are stored as nodes.

Each node contains a data field, and a next field: points to the next node.

As shown in the figure: it is found that each node of each linked list is not necessarily continuous storage.

The linked list is divided into the linked list of the leading node and the linked list without the header node, which is determined according to the actual demand.

Introduction to single linked list

The schematic diagram of the logical structure of the single linked list (lead node) is as follows

Application example of single linked list

Using an one-way linked list with a head header-Water margin Heroes list Management

Package com.structures.linkedlist; public class SingleLinkedListDemo {public static void main (String [] args) {HeroNode heroNode1 = new HeroNode (1, "Song Jiang", "timely rain"); HeroNode heroNode2 = new HeroNode (2, "Lu Junyi", "Jade Kirin"); HeroNode heroNode3 = new HeroNode (3, "Wu Yong", "Zhi Duoxing"); HeroNode heroNode4 = new HeroNode (4, "Lin Chong", "Leopard head") SingleLinkedList singleLinkedList = new SingleLinkedList (); singleLinkedList.add (heroNode3); singleLinkedList.add (heroNode2); singleLinkedList.add (heroNode4); singleLinkedList.add (heroNode1); singleLinkedList.list () }} / / define SingleLinkedList management our hero class SingleLinkedList {/ / initialize a header node first, the header node cannot be moved, and the future traversal uses private HeroNode head = new HeroNode (0, ","); / / add nodes to the one-way linked list / / idea: when the order of numbering is not considered / / 1. Find the last node of the current linked list / / 2. Point the nextfield of the last node to the new node public void add (HeroNode node) {/ / because the head node cannot be moved, so we need an auxiliary traversal temp HeroNode temp = head / / iterate through the linked list and find the last while (temp.next! = null) {/ / find the last / / if temp is not found, move back to temp = temp.next;} temp.next = node } / / display linked list [traversal] public void list () {/ / determine whether the linked list is empty if (head.next = = null) {System.out.println ("empty list");} / / because the header node cannot move, so we need an auxiliary variable to traverse HeroNode temp = head.next While (temp! = null) {/ / determine whether the information of the last / / output node is System.out.println (temp); / / move the temp back to temp = temp.next;} / / define a HeroNode, and each HeroNode object is a node class HeroNode {public int no; public String name Public String nickName; public HeroNode next;// points to the next node / / constructor public HeroNode (int no, String name, String nickName) {this.no = no; this.name = name; this.nickName = nickName;} public HeroNode getNext () {return next;} public void setNext (HeroNode next) {this.next = next } @ Override public String toString () {return "HeroNode {" + "no=" + no + ", name='" + name +'\'+ ", nickName='" + nickName +'\'+'}' }} / * HeroNode {no=3, name=' Wu Yong', nickName=' Zhiduoxing'} HeroNode {no=2, name=' Lu Junyi, nickName=' Yuqilin'} HeroNode {no=4, name=' Lin Chong, nickName=' Panzi head'} HeroNode {no=1, name=' Song Jiang', nickName=' timely Rain'} * /

You can see the implementation of the above linked list. When adding heroes, they are not sorted by the number of heroes. Let's rewrite an add method to sort by number when inserting heroes.

Package com.structures.linkedlist; public class SingleLinkedListDemo {public static void main (String [] args) {HeroNode heroNode1 = new HeroNode (1, "Song Jiang", "timely rain"); HeroNode heroNode2 = new HeroNode (2, "Lu Junyi", "Jade Kirin"); HeroNode heroNode3 = new HeroNode (3, "Wu Yong", "Zhi Duoxing"); HeroNode heroNode4 = new HeroNode (4, "Lin Chong", "Leopard head") SingleLinkedList singleLinkedList = new SingleLinkedList (); singleLinkedList.addByNo (heroNode3); singleLinkedList.addByNo (heroNode2); singleLinkedList.addByNo (heroNode4); singleLinkedList.addByNo (heroNode1); singleLinkedList.list () }} / / define SingleLinkedList management our hero class SingleLinkedList {/ / initialize a header node first, the header node cannot be moved, and the future traversal uses private HeroNode head = new HeroNode (0, ","); / / add nodes to the one-way linked list / / idea: when the order of numbering is not considered / / 1. Find the last node of the current linked list / / 2. Point the nextfield of the last node to the new node public void add (HeroNode node) {/ / because the head node cannot be moved, so we need an auxiliary traversal temp HeroNode temp = head / / iterate through the linked list and find the last while (temp.next! = null) {/ / find the last / / if temp is not found, move back to temp = temp.next;} temp.next = node } / / the second way to add heroes, when adding heroes, insert the heroes to the specified position according to the ranking / / if there is such a ranking, the addition fails, and gives a hint public void addByNo (HeroNode heroNode) {/ / because the head node cannot be moved, so we need an auxiliary traversal temp / / because the single linked list Therefore, the temp you are looking for is located in the previous node in the add location, otherwise you cannot join HeroNode temp = head. Boolean flag = false;// identifies whether the added number exists. By default, false while (true) {if (temp.next = = null) {break;} if (temp.next.no > heroNode.no) {/ / is found, and break is inserted after the temp. } else if (temp.next.no = = heroNode.no) {/ / number already exists flag = true; break;} temp = temp.next } if (flag) {System.out.printf ("the hero's number% d already exists and cannot be added\ n", heroNode.no);} else {/ / insert heroNode.next = temp.next; temp.next = heroNode after the linked list temp }} / / Show linked list [traverse] public void list () {/ / determine whether the linked list is empty if (head.next = = null) {System.out.println ("empty list");} / / because the header node cannot be moved, we need an auxiliary variable to traverse HeroNode temp = head.next While (temp! = null) {/ / determine whether the information of the last / / output node is System.out.println (temp); / / move the temp back to temp = temp.next;} / / define a HeroNode, and each HeroNode object is a node class HeroNode {public int no; public String name Public String nickName; public HeroNode next;// points to the next node / / constructor public HeroNode (int no, String name, String nickName) {this.no = no; this.name = name; this.nickName = nickName;} public HeroNode getNext () {return next;} public void setNext (HeroNode next) {this.next = next } @ Override public String toString () {return "HeroNode {" + "no=" + no + ", name='" + name +'\'+ ", nickName='" + nickName +'\'+'}' }} / * HeroNode {no=1, name=' Song Jiang', nickName=' timely rain'} HeroNode {no=2, name=' Lu Junyi, nickName=' Yuqilin'} HeroNode {no=3, name=' Wu Yong', nickName=' Zhiduoxing'} HeroNode {no=4, name=' Lin Chong, nickName=' Leopard head'} * /

Improve the function again, add and modify the node function

/ / modify the information of the node according to the no number, that is, the number no cannot be modified. Public void update (HeroNode heroNode) {/ / determine whether if (head.next = = null) {System.out.println ("linked list is empty");} / / find the node that needs to be modified, according to the no number HeroNode temp = head.next; boolean flag = false / / indicates whether the node has found while (true) {if (temp = = null) {break;} if (temp.no = = heroNode.no) {flag = true; break;} temp = temp.next } if (flag) {temp.name = heroNode.name; temp.nickName = heroNode.nickName;} else {System.out.printf ("Node numbered% d not found, cannot be modified\ n", heroNode.no);}}

Improve the function again, add and delete node function

/ / Delete node public void remove (HeroNode heroNode) {/ / determine whether if is empty (head.next = = null) {System.out.println ("linked list is empty");} HeroNode temp = head.next; boolean flag = false / / identify whether the point to be deleted while (true) {if (temp = = null) {break;} if (temp.next.no = = heroNode.no) {flag = true; break;} temp = temp.next is found } if (flag) {temp.next = temp.next.next;} else {System.out.printf ("cannot delete node numbered% d,\ n", heroNode.no);}}

Once again, improve the function and add the effective node number function of the statistical single linked list.

/ * get the number of valid nodes of a single linked list without counting the number of head nodes of * @ param head linked list * @ return effective nodes * / public static int getLength (HeroNode head) {if (head.next = = null) {return 0;} int count = 0; HeroNode temp = head.next While (temp.next! = null) {count++; temp = temp.next;} return count;}

Once again, improve the function and add the function of finding the penultimate node in the single linked list

/ * * find the penultimate node of the single linked list [Sina interview questions] * train of thought: * 1. First, traverse the list from beginning to end to get the total length of the list * 2. After you get the size, you can iterate from the first of the linked list to (size-index), and you can get * * @ param head * @ param index which represents the penultimate index node * @ return * / public static HeroNode findLastIndexNode (HeroNode head, int index) {if (head.next = = null) {return null;} int size = getLength (head). If (index size) {return null;} HeroNode temp = head.next; for (int I = 0; I

< (size - index); i++) { temp = temp.next; } return temp; } 再次进行完善功能,添加单链表反转功能 /** * 反转链表[腾讯面试题] * 思路: * 1.先定义一个reverseHead = new HeroHead(); * 2.从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表的最前端; * 3.原来的链表的head.next = reverseHead.next; */ public static void reverseList(HeroNode head) { if (head.next == null || head.next.next == null) { return; } HeroNode curr = head.next; HeroNode next = null;//指向当前节点[curr]的下一个节点 HeroNode reverseHead = new HeroNode(0, "", ""); while (curr != null) { next = curr.next;//先暂时保存curr节点的下一个节点 curr.next = reverseHead.next;//将curr的下一个节点指向新的链表的最前端 reverseHead.next = curr;//将curr连接到新的链表上 curr = next;//让curr后移 } head.next = reverseHead.next; } 再次进行完善功能,添加从尾到头打印单链表功能 /** * 使用栈的方式逆序打印[百度面试题] */ public static void reversePrint(HeroNode head) { if (head.next == null) { return; } Stack heroNodes = new Stack(); HeroNode temp = head.next; while (temp != null) { heroNodes.add(temp); temp = temp.next; } while (heroNodes.size() >

0) {System.out.println (heroNodes.pop ());}} about how to use a single linked list to share the internal skills of Java programming, I hope the above content can be helpful to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.