链表分为单链表,双向链表和循环链表,是一种链式存储结构,由一个个结点链式构成,结点包含数据域和指针域,其中单链表是只有一个指向后驱结点的指针,双向链表除头结点和尾结点外,每个结点都有一个前驱指针和一个后继指针,循环链表的尾结点的指针指向头结点.
相比数组而言,链表的插入和删除比较快,查询慢.
本文主要以单链表为例,介绍下链表的常用算法操作.
单链表的结构:
在java语言中,链表的每个结点用Node类来表示:
package com.linkedlist;public class Node { private int data;// 结点数据 private Node next;// 下一个结点 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; }}
定义一个链表操作类,里面包含常用的操作:
package com.linkedlist;import java.util.Hashtable;public class LinkedListOperator { private Node head = null;// 头结点 // 在链表的末尾增加一个结点 private void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node temp = head; while (temp.getNext() != null) { temp = temp.getNext(); } temp.setNext(newNode); } // 打印链表结点 private void printLink() { Node curNode = head; while (curNode != null) { System.out.println(curNode.getData()); curNode = curNode.getNext(); } System.out.println("==========="); } // 求链表长度 private int getLength() { int len = 0; Node curNode = head; while (curNode != null) { len++; curNode = curNode.getNext(); } return len; } // 删除某一个结点 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(); } } // 去掉重复元素 private void distinctLink() { Hashtable<Integer, Integer> map = new Hashtable<Integer, Integer>(); 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(); } } // 返回倒数第k个结点,定义两个指针,第一个指针向前移动K-1次,之后两个指针同时前进, // 当第一个指针到达末尾时,第二个指针所在的位置即为倒数第k个结点 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(); }}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
本文标题: Java实现链表的常见操作算法详解
以上就上有关Java实现链表的常见操作算法详解的全部内容，学步园全面介绍编程技术、操作系统、数据库、web前端技术等内容。