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

Editor to share with you how to achieve Java linked list, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to understand it!

The linked list is divided into single linked list, bi-directional linked list and circular linked list, which is a kind of linked storage structure, which is composed of node linked structure, and the node contains data field and pointer domain, in which the single linked list has only one pointer to the rear driving node. in the two-way linked list, except for the head node and the tail node, each node has a leading pointer and a follow-up pointer, and the pointer of the tail node of the circular linked list points to the head node.

Compared with arrays, the insertion and deletion of linked lists are faster and the query is slow.

This paper mainly introduces the common algorithm operation of the lower linked list by taking the single linked list as an example.

Structure of single linked list:

In the Java language, each node of a linked list is represented by a Node class:

Package com.linkedlist;public class Node {private int data;// Node data private Node next;// next node public Node (int data) {this.data = data;} public int getData () {return data;} public void setData (int data) {this.data = data;} public Node getNext () {return next;} public void setNext (Node next) {this.next = next;}}

Define a linked list operation class that contains common operations:

Package com.linkedlist;import java.util.Hashtable;public class LinkedListOperator {private Node head = null;// header node / / add a node private void addNode (int data) {Node newNode = newNode (data) at the end of the linked list; if (head = = null) {head = newNode; return;} Node temp = head; while (temp.getNext ()! = null) {temp = temp.getNext () } temp.setNext (newNode);} / print linked list node private void printLink () {Node curNode = head; while (curNode! = null) {System.out.println (curNode.getData ()); curNode = curNode.getNext ();} System.out.println ("=");} / / find the list length private int getLength () {int len = 0; Node curNode = head While (curNode! = null) {len++; curNode = curNode.getNext ();} return len;} / / Delete a node private boolean delNode (int index) {if (index)

< 1) { return false; } if (index == 1) { head = head.getNext(); return true; } Node preNode = head; Node curNode = head.getNext(); int n = 1; while (curNode.getNext() != null) { if (n == index) { preNode.setData(curNode.getData()); preNode.setNext(curNode.getNext()); return true; } preNode = preNode.getNext(); curNode = curNode.getNext(); n++; } if (curNode.getNext() == null) { preNode.setNext(null); } return false; } // 链表排序:选择排序法,从小到大 private void sortList() { Node curNode = head; while (curNode != null) { Node nextNode = curNode.getNext(); while (nextNode != null) { if (curNode.getData() >

NextNode.getData () {int temp = curNode.getData (); curNode.setData (nextNode.getData ()); nextNode.setData (temp);} nextNode = nextNode.getNext ();} curNode = curNode.getNext ();}} / / remove the repeating element private void distinctLink () {Hashtable map = new Hashtable (); Node curNode = head; Node preNode = null While (curNode! = null) {if (map.containsKey (curNode.getData () {preNode.setData (curNode.getData ()); preNode.setNext (curNode.getNext ());} else {map.put (curNode.getData (), 1); preNode = curNode;} curNode = curNode.getNext () }} / / returns the last-to-last node and defines two pointers. The first pointer moves forward once, and then the two pointers advance simultaneously. / / when the first pointer reaches the end, the position of the second pointer is the penultimate node private Node getReverNode (int k) {if (k).

< 1) { return null; } Node first = head; Node second = head; for (int i = 0; i < k - 1; i++) { first = first.getNext(); } while (first.getNext() != null) { first = first.getNext(); second = second.getNext(); } return second; } // 反转链表 private void reserveLink() { Node preNode = null; Node curNode = head; Node tempNode = null; while (curNode != null) { tempNode = curNode.getNext(); curNode.setNext(preNode); preNode = curNode; curNode = tempNode; } head = preNode; } // 寻找链表的中间结点 private Node getMiddleNode() { Node slowNode = head; Node quickNode = head; while (slowNode.getNext() != null && quickNode.getNext() != null) { slowNode = slowNode.getNext(); quickNode = quickNode.getNext().getNext(); } return slowNode; } // 判断链表是否有环 private boolean isRinged() { if (head == null) { return false; } Node slowNode = head; Node quickNode = head; while (slowNode.getNext() != null && quickNode.getNext() != null) { slowNode = slowNode.getNext(); quickNode = quickNode.getNext().getNext(); if (slowNode.getData() == quickNode.getData()) { return true; } } return false; } // 删除指定结点 private boolean delNode(Node node) { if (node.getNext() == null) { return false;// 在不知道头结点的情况下,没法删除单链表的尾结点 } node.setData(node.getNext().getData()); node.setNext(node.getNext().getNext()); return true; } // 判断两个链表是否相交:相交的链表的尾结点相同 private boolean isCross(Node n1, Node n2) { while (n1.getNext() != null) { n1 = n1.getNext(); } while (n2.getNext() != null) { n2 = n2.getNext(); } if (n1.getData() == n2.getData()) { return true; } return false; } // 求相交链表的起始点 private Node getFirstCrossNode(LinkedListOperator l1, LinkedListOperator l2) { int len = l1.getLength() - l2.getLength(); Node n1 = l1.head; Node n2 = l2.head; if (len >

0) {for (int I = 0; I < len; I ()) {N1 = n1.getNext ();}} else {for (int I = 0; I < len; I +) {N2 = n2.getNext ();}} while (n1.getData ()! = n2.getData ()) {N1 = n1.getNext (); N2 = n2.getNext ();} return N1 } public static void main (String [] args) {LinkedListOperator llo = new LinkedListOperator (); llo.addNode (10); llo.addNode (4); llo.addNode (6); llo.addNode (8); llo.printLink (); / / llo.delNode (4); / / llo.sortList (); / / llo.distinctLink (); / / System.out.println (llo.getReverNode (3). GetData ()); / / llo.reserveLink () / / System.out.println (llo.getMiddleNode (). GetData ()); / System.out.println (llo.isRinged ()); llo.delNode (llo.head.getNext (). GetNext ()); llo.printLink ();}} these are all the contents of the article "how to implement linked lists in Java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.