Implementation of basic operations of Java singly linked list

I was recently asked about linked lists when a friend and I were discussing Java. To be honest, I have learned very little in the nearly one year I have been learning programming. I learned Java and C# as languages, and learned a little about Html+css+javascript about the Web. Because of my preference, I am more serious when learning WinForm, and I also do some research on database operations. But I have never studied or researched linked lists. In addition, I have recently been studying WPF, and the course has also reached JSP, which is relatively tight.

But I still took one night and half a day to look at the one-way linked list. And I tried to write an example using Java. Friends who have never been exposed to linked lists can use it as a reference. I hope you can provide more valuable opinions.

Let’s first explain what a linked list is. As far as I know, a linked list is a data structure, the same level as an array. For example, the ArrayList we use in Java is implemented based on an array. The implementation principle of LinkedList is linked list. My teacher said that linked lists are not efficient when performing loop traversal, but they have obvious advantages when inserting and deleting. Then he has more than ten years of programming experience, I believe it. But I don’t know if he is talking about doubly linked lists. Here we only have an understanding of one-way linked lists.

Linked lists (the linked lists mentioned in this article are all one-way linked lists, hereafter referred to as one-way linked lists) are actually composed of nodes (Node), and a linked list has an indefinite number of nodes. There is only one head node (Head) exposed to the outside. All our operations on the linked list are performed directly or indirectly through its head node.

Node is composed of an object that needs to be stored and a reference to the next node. In other words, the node has two members: the stored object and the reference to the next node.

Maybe you don’t understand it this way, so I’ll post a picture and it may be easier for you to understand.

The key code to implement the basic operations of Java singly linked list is as follows:

package com.tyxh.link; 
//节点类 
public class Node { 
protected Node next; //指针域 
protected int data;//数据域 
public Node( int data) { 
this. data = data; 
} 
//显示此节点 
public void display() { 
System. out.print( data + " "); 
} 
} 
package com.tyxh.link; 
//单链表 
public class LinkList { 
public Node first; // 定义一个头结点 
private int pos = 0;// 节点的位置 
public LinkList() { 
this. first = null; 
} 
// 插入一个头节点 
public void addFirstNode( int data) { 
Node node = new Node(data); 
node. next = first; 
first = node; 
} 
// 删除一个头结点,并返回头结点 
public Node deleteFirstNode() { 
Node tempNode = first; 
first = tempNode. next; 
return tempNode; 
} 
// 在任意位置插入节点 在index的后面插入 
public void add(int index, int data) { 
Node node = new Node(data); 
Node current = first; 
Node previous = first; 
while ( pos != index) { 
previous = current; 
current = current. next; 
pos++; 
} 
node. next = current; 
previous. next = node; 
pos = 0; 
} 
// 删除任意位置的节点 
public Node deleteByPos( int index) { 
Node current = first; 
Node previous = first; 
while ( pos != index) { 
pos++; 
previous = current; 
current = current. next; 
} 
if(current == first) { 
first = first. next; 
} else { 
pos = 0; 
previous. next = current. next; 
} 
return current; 
} 
// 根据节点的data删除节点(仅仅删除第一个) 
public Node deleteByData( int data) { 
Node current = first; 
Node previous = first; //记住上一个节点 
while (current. data != data) { 
if (current. next == null) { 
return null; 
} 
previous = current; 
current = current. next; 
} 
if(current == first) { 
first = first. next; 
} else { 
previous. next = current. next; 
} 
return current; 
} 
// 显示出所有的节点信息 
public void displayAllNodes() { 
Node current = first; 
while (current != null) { 
current.display(); 
current = current. next; 
} 
System. out.println(); 
} 
// 根据位置查找节点信息 
public Node findByPos( int index) { 
Node current = first; 
if ( pos != index) { 
current = current. next; 
pos++; 
} 
return current; 
} 
// 根据数据查找节点信息 
public Node findByData( int data) { 
Node current = first; 
while (current. data != data) { 
if (current. next == null) 
return null; 
current = current. next; 
} 
return current; 
} 
} 
package com.tyxh.link; 
//测试类 
public class TestLinkList { 
public static void main(String[] args) { 
LinkList linkList = new LinkList(); 
linkList.addFirstNode(20); 
linkList.addFirstNode(21); 
linkList.addFirstNode(19); 
//19,21,20 
linkList.add(1, 22); //19,22,21,20 
linkList.add(2, 23); //19,22,23,21,20 
linkList.add(3, 99); //19,22,23,99,21,20 
linkList.displayAllNodes(); 
// Node node = linkList.deleteFirstNode(); 
// System.out.println("node : " + node.data); 
// linkList.displayAllNodes(); 
// node = linkList.deleteByPos(2); 
// System.out.println("node : " + node.data); 
// linkList.displayAllNodes(); 
// linkList.deleteFirstNode(); 
Node node = linkList.deleteByData(19); 
// Node node = linkList.deleteByPos(0); 
System. out.println( "node : " + node. data); 
linkList.displayAllNodes(); 
Node node1 = linkList.findByPos(0); 
System. out.println( "node1: " + node1. data); 
Node node2 = linkList.findByData(22); 
System. out.println( "node2: " + node2. data); 
} 
}

The above is the basic operation of Java singly linked list introduced by the editor. I hope it will be helpful to everyone. If you have any questions, please leave me a message and the editor will reply to you in time. I would also like to thank you all for your support of the PHP Chinese website!

For more articles related to the implementation of basic operations of Java singly linked lists, please pay attention to the PHP Chinese website!