Java实现链表的常见操作算法详解

Java实现链表的常见操作算法详解

链表分为单链表,双向链表和循环链表,是一种链式存储结构,由一个个结点链式构成,结点包含数据域和指针域,其中单链表是只有一个指向后驱结点的指针,双向链表除头结点和尾结点外,每个结点都有一个前驱指针和一个后继指针,循环链表的尾结点的指针指向头结点.

相比数组而言,链表的插入和删除比较快,查询慢.

本文主要以单链表为例,介绍下链表的常用算法操作.

单链表的结构:

在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 curNoTvPtFDwSTde = 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 (nextNhttp://ode != 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 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();

}

}

// 返回倒数第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()) {

TvPtFDwST 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();

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。