首页 >java编程 >java实现链表

java实现链表

来源:www.hellomonster.net 时间:2024-05-14 03:18:40 作者:第一编程网 浏览: [手机版]

  链表是一种见的据结构,它由一系列节点组成,每个节点包含据和指向下一个节点的指针第一编程网。链表的优点是可以动态地添和删除节点,而不需要像组一样预留固间。本文将介绍如何使用Java实现链表。

java实现链表(1)

1. 义节点类

首先,我们需要义一个节点类,它包含两个属性:据和指向下一个节点的指针。代码如下:

  ```

  public class ListNode {

  int val;

  ListNode next;

  public ListNode(int val) {

  this.val = val;

  this.next = null;

  }

}

  ```

2. 实现链表

  接下来,我们需要实现链表类。链表类包含两个属性:节点和链表长度。节点是链表中第一个节点,链表长度表示链表中节点的个。代码如下:

```

  public class MyLinkedList {

  private ListNode head;

  private int size;

  public MyLinkedList() {

  this.head = null;

  this.size = 0;

}

  }

  ```

java实现链表(2)

3. 实现添节点方法

链表的添节点方法包括在链表末尾添节点和在链表指位置添节点。我们先来实现在链表末尾添节点的方法。代码如下:

  ```

  public void addAtTail(int val) {

  ListNode newNode = new ListNode(val);

  if (head == null) {

head = newNode;

} else {

ListNode cur = head;

while (cur.next != null) {

  cur = cur.next;

  }

cur.next = newNode;

  }

  size++;

  }

```

在这个方法中,我们首先创建一个新节点,然后判断链表是否为。如果链表为,将节点指向新节点第.一.编.程.网。如果链表不为,遍链表直到找到最后一个节点,将最后一个节点的指针指向新节点。最后,链表长度1。

  接下来,我们来实现在链表指位置添节点的方法。代码如下:

  ```

  public void addAtIndex(int index, int val) {

  if (index size) {

  return;

  }

if (index == 0) {

  addAtHead(val);

  } else if (index == size) {

addAtTail(val);

  } else {

ListNode newNode = new ListNode(val);

ListNode prev = head;

  for (int i = 0; i < index - 1; i++) {

prev = prev.next;

  }

newNode.next = prev.next;

prev.next = newNode;

  size++;

  }

}

  ```

在这个方法中,我们首先判断插入位置是否合法。如果插入位置小于0或大于链表长度,直接返。如果插入位置等于0,调用addAtHead方法。如果插入位置等于链表长度,调用addAtTail方法。否则,遍链表找到插入位置的前一个节点,然后将新节点插入到前一个节点和后一个节点之间。最后,链表长度1。

java实现链表(3)

4. 实现删除节点方法

  链表的删除节点方法包括删除链表节点、删除链表尾节点和删除链表指位置的节点hellomonster.net。我们先来实现删除链表节点的方法。代码如下:

  ```

  public void deleteAtHead() {

  if (head == null) {

return;

}

  head = head.next;

size--;

}

```

  在这个方法中,我们首先判断链表是否为。如果链表为,直接返。否则,将节点指向下一个节点,链表长度减1。

  接下来,我们来实现删除链表尾节点的方法。代码如下:

  ```

  public void deleteAtTail() {

  if (head == null) {

  return;

  }

if (head.next == null) {

  head = null;

  } else {

ListNode prev = head;

  while (prev.next.next != null) {

  prev = prev.next;

  }

prev.next = null;

}

  size--;

  }

  ```

在这个方法中,我们首先判断链表是否为。如果链表为,直接返。如果链表只一个节点,将节点置为null。否则,遍链表找到倒第二个节点,将其指针指向null。最后,链表长度减1原文www.hellomonster.net

  最后,我们来实现删除链表指位置的节点的方法。代码如下:

  ```

public void deleteAtIndex(int index) {

if (index = size) {

return;

}

  if (index == 0) {

  deleteAtHead();

  } else if (index == size - 1) {

  deleteAtTail();

} else {

  ListNode prev = head;

  for (int i = 0; i < index - 1; i++) {

  prev = prev.next;

}

prev.next = prev.next.next;

size--;

  }

  }

  ```

  在这个方法中,我们首先判断删除位置是否合法。如果删除位置小于0或大于等于链表长度,直接返。如果删除位置等于0,调用deleteAtHead方法。如果删除位置等于链表长度减1,调用deleteAtTail方法。否则,遍链表找到删除位置的前一个节点,然后将前一个节点的指针指向删除位置的后一个节点。最后,链表长度减1。

5. 实现其方法

  除了添节点和删除节点方法,链表还包括获取节点值、获取链表长度和打印链表等方法。我们来一一实现。

  获取节点值方法:

  ```

  public int get(int index) {

if (index = size) {

  return -1;

}

ListNode cur = head;

for (int i = 0; i < index; i++) {

  cur = cur.next;

  }

return cur.val;

}

```

  在这个方法中,我们首先判断获取位置是否合法www.hellomonster.net第一编程网。如果获取位置小于0或大于等于链表长度,返-1。否则,遍链表找到获取位置的节点,并返其值。

  获取链表长度方法:

  ```

  public int size() {

  return size;

  }

  ```

  在这个方法中,我们直接返链表长度。

打印链表方法:

```

  public void printList() {

  ListNode cur = head;

while (cur != null) {

  System.out.print(cur.val + " ");

  cur = cur.next;

  }

  System.out.println();

  }

  ```

  在这个方法中,我们遍链表并打印每个节点的值。

6. 测试链表类

最后,我们来测试链表类的各个方法。代码如下:

```

  public static void main(String[] args) {

  MyLinkedList list = new MyLinkedList();

  list.addAtHead(1);

list.addAtTail(3);

  list.addAtIndex(1, 2);

System.out.println(list.get(1)); // 2

  list.deleteAtIndex(1);

System.out.println(list.get(1)); // 3

  list.printList(); // 1 3

  System.out.println(list.size()); // 2

}

```

在这个测试代码中,我们首先创建一个链表对象list,然后向链表中添节点。接着,测试获取节点值方法和删除节点方法。最后,测试打印链表和获取链表长度方法。

  至此,我们已经完成了链表类的实现。链表是一种见的据结构,掌握链表的实现方法对于程序员来说是非重要的www.hellomonster.net

0% (0)
0% (0)
标签:实现链表
版权声明:《java实现链表》一文由第一编程网(www.hellomonster.net)网友投稿,不代表本站观点,版权归原作者本人所有,转载请注明出处,如有侵权、虚假信息、错误信息或任何问题,请尽快与我们联系,我们将第一时间处理!

我要评论

评论 ( 0 条评论)
网友评论仅供其表达个人看法,并不表明好好孕立场。
最新评论

还没有评论,快来做评论第一人吧!
相关文章
  • java邮件发送失败怎么解决

    Java邮件发送失败是一个常见的问题,可能是由于多种原因造成的,比如网络问题、SMTP服务器设置问题、邮件内容问题等等。在这篇文章中,我们将介绍如何解决Java邮件发送失败的问题。一、检查网络连接Java邮件发送需要网络连接,如果网络连接不稳定或者中断,就会导致邮件发送失败。因此,首先要检查网络连接是否正常。

    [ 2024-05-14 02:30:30 ]
  • Java数组大小

    Java是一种面向对象的编程语言,数组是Java中最常用的数据结构之一。在Java中,数组是一种固定大小的数据结构,它可以存储同一类型的数据。数组的大小在创建时就已经确定,一旦创建后就不能改变。Java数组的大小可以通过其长度属性来确定。数组的长度是在创建数组时指定的,可以通过数组名.length来获得。例如,下面的代码创建了一个长度为5的整数数组:

    [ 2024-05-14 02:18:53 ]
  • java中高级面试题及答案

    Java作为一门广泛应用于企业级开发的编程语言,其面试题也是十分丰富的。以下是一些Java中高级面试题及其答案,供大家参考。1. 什么是Java中的反射机制?它有什么作用?Java中的反射机制是指在程序运行时,可以动态地获取类的信息,包括类的属性、方法、构造方法等,并可以在运行时调用这些信息。

    [ 2024-05-14 01:28:50 ]
  • java随机数重复怎么解决

    随机数在计算机科学中是一个非常重要的概念,它被广泛应用于密码学、模拟、游戏开发等领域。但是,随机数的生成并不总是完全随机的,有时会出现重复的情况。那么,如何解决Java中随机数重复的问题呢?本文将从以下几个方面进行介绍。一、随机数的生成原理

    [ 2024-05-14 01:16:59 ]
  • java获取路径下所有文件

    Java是一种面向对象编程语言,常用于Web应用程序开发、移动应用程序开发、桌面应用程序开发等。在Java应用程序中,经常需要读取或处理文件,因此获取路径下所有文件是一个常见的需求。Java提供了File类来处理文件和目录。File类提供了许多方法来获取文件和目录的信息,包括文件名、路径、大小、修改时间等。下面介绍几种获取路径下所有文件的方法。

    [ 2024-05-14 01:03:14 ]
  • java显示非法字符

    1. Java中的非法字符Java中的非法字符指的是不符合Java语法规则的字符。例如,Java中的标识符只能由字母、数字、下划线和美元符号组成,而不能包含其他字符。如果在Java代码中出现了非法字符,编译器会报错,提示“非法字符”。2. Java中的字符编码

    [ 2024-05-14 00:26:51 ]
  • java语言是哪个公司的产品

    Java语言是一种高级编程语言,由Sun Microsystems公司于1995年推出。现在Java语言的发展和维护由Oracle公司负责。Java语言的特点是跨平台、面向对象、安全、简单易学等,因此广泛应用于Web开发、移动应用、游戏开发等领域。Java语言的起源

    [ 2024-05-13 23:02:02 ]
  • 两个队列实现栈java

    在Java中,我们可以使用两个队列来实现栈。这种方法的基本思想是:使用两个队列,一个队列用于存储元素,另一个队列用于辅助操作。我们可以使用以下步骤来实现该算法:1. 创建两个队列Q1和Q2。2. 将元素添加到Q1中。3. 当需要弹出元素时,将Q1中的所有元素移动到Q2中,直到Q1中只剩下一个元素。4. 弹出Q1中的最后一个元素。

    [ 2024-05-13 22:12:18 ]
  • java反编译能拿到源码吗

    Java反编译是指将Java字节码文件(.class文件)反向转换成Java源代码文件(.java文件),以便于开发人员对程序进行分析和修改。Java反编译工具可以帮助开发人员了解程序的实现细节,但同时也可能会被黑客用于恶意攻击。因此,在使用Java反编译工具时,需要注意一些安全问题。一、Java反编译的原理

    [ 2024-05-13 20:31:55 ]
  • javaweb应用的目录结构

    JavaWeb应用的目录结构是指在开发JavaWeb应用时,所需要遵循的目录结构规范。这个规范是为了方便开发者进行开发和维护而制定的,同时也有利于保证应用的可移植性和可扩展性。一、目录结构JavaWeb应用的目录结构通常包括以下几个目录:

    [ 2024-05-13 19:12:21 ]