当前位置: 首页 > 编程笔记 >

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

谭新知
2023-03-14
本文向大家介绍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 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单链表基本操作的实现的使用技巧和注意事项,需要的朋友参考一下 最近被问到链表,是一个朋友和我讨论Java的时候说的。说实话,我学习编程的近一年时间里,学到的东西还是挺少的。语言是学了Java和C#,关于Web的学了一点Html+css+javascript。因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究。但链表这个东西

  • 本文向大家介绍PHP实现链式操作的三种方法详解,包括了PHP实现链式操作的三种方法详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了PHP实现链式操作的三种方法。分享给大家供大家参考,具体如下: 在php中有很多字符串函数,例如要先过滤字符串收尾的空格,再求出其长度,一般的写法是: 如果要实现类似js中的链式操作,比如像下面这样应该怎么写? 下面分别用三种方式来实现: 方法一、使用魔法函

  • 本文向大家介绍C语言单链表常见操作汇总,包括了C语言单链表常见操作汇总的使用技巧和注意事项,需要的朋友参考一下 C语言的单链表是常用的数据结构之一,本文总结了单链表的常见操作,实例如下:

  • 本文向大家介绍jQuery常见的遍历DOM操作详解,包括了jQuery常见的遍历DOM操作详解的使用技巧和注意事项,需要的朋友参考一下 本文实例总结了jQuery常见的遍历DOM操作。分享给大家供大家参考,具体如下: 向上遍历DOM树 .parent():返回被选元素的直接父元素,该方法只会向上一级对DOM树进行遍历 .parents():返回被选元素的所有祖先元素,一直向上遍历,直到文档的根元素

  • 本文向大家介绍JS浏览器BOM常见操作实例详解,包括了JS浏览器BOM常见操作实例详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了JS浏览器BOM常见操作。分享给大家供大家参考,具体如下: window尺寸 有三种方法能够确定浏览器窗口的尺寸(浏览器的视口,不包括工具栏和滚动条)。 对于Internet Explorer、Chrome、Firefox、Opera 以及 Safari:

  • 本文向大家介绍使用python实现链表操作,包括了使用python实现链表操作的使用技巧和注意事项,需要的朋友参考一下 一、概念梳理 链表是计算机科学里面应用应用最广泛的数据结构之一。它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧、环形缓冲和队列) 简单的说,一个列表就是单数据通过索引集合在一起。在C里面这叫做指针。比方说,一个数据元素可以由地址元素,地理元素、路由信息活着交易细节等