Java实现单链表的操作

本文实例为大家分享了java实现单链表的基本操作，供大家参考，具体内容如下

顺序表：物理上逻辑上都连续；
链表：物理上不一定连续，逻辑上一定连续的。

链表的概念及结构

概念：连表示一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是用过链表中的引用链接次序实现的。

8种链表结构：

单项、双向
带头、不带头
循环、非循环

主要的三种链表：

无头单项非循环链表、带头循环单链表、不带头双向循环链表

代码实现

1. 接口定义

package com.github.linked.impl;public interface ilinked {  // 头插法  void addfirst(int data);  // 尾插法  void addlast(int data);  // 任意位置插入，第一数据节点为0号下标  boolean addindex(int index, int data);  // 查找是否包含关键字 key 在单链表中  boolean contains(int key);  // 删除第一次出现的关键字为 key 的节点  int remove(int key);  // 删除所有值为 key 的节点  void removeallkey(int key);  // 得到单链表的长度  int getlength();  // 打印单链表  void display();  // 清空单链表以防内存泄漏  void clear();}

2. 代码实现接口

package com.github.linked.impl;public class singlelisted implements ilinked {  // 节点类  class node {    private int data;    private node next;    public node(int data) {      this.data = data;      this.next = next;    }  }  private node head; //头节点  public singlelisted() {    this.head = head;  }  /**  * 头插法  * @param data 要插入的数据  */  @override  public v孕妇可以吃鳝鱼吗oid addfirst(int data) {    // 1. 拿到一个实体    node node = new node(data);    // 2. 插入    // 如果是第一次插入，直接到头节点    if (this.head == null) {      this.head = node;    } el { //不是第一次插入      node.next = this.head; // 插入的节点指向头节点      this.head = node;   // 更新头节点    }  }  /**  * 尾插法  * @param data 要插入的数据  */  @override  public void addlast(int data) {    // 1. 拿到一个实体    node node = new node(data);    node cur = this.head;    // 2. 插入    // 如果是第一次插入，直接到头节点    if (this.head == null) {      this.head = node;    } el {      // 找尾巴      while (cur.next != null) {        cur = cur.next;      }      // 退出上面的循环，cur所执行的位置就是尾节点      cur.next = 活动方案怎么做node;    }  }  // 检测 index 该下标是否合法  private void checkindex(int index) {    if (index < 0 || index > getlength())      throw new indexoutofboundxception("下标不合法！");  }  // 找到下标为 index-1 位置的节点  private node archindex(int index) {    checkindex(index);    if (index == 0)      return null;    int count = 0; // 记录行走的步数    node cur = this.head;    while (cur.next != null && count < index-1) {      cur = cur.next;      count++;    }    return cur;  }  /**  * 任意位置插入，第一数据节点为 0号下标  * @param index 插入的下标  * @param data 要插入的数据  * @return true  */  @override  public boolean addindex(int index, int data) {    node node = new node(data);    node cur = archindex(index);    // 如果链表为空，直接插入到头节点    if (cur == null) {      node.next = thi以光先帝遗德s.head;      this.head = node;    } el { // 链表不为空，插入到 cur 的位置处      node.next = cur.next; // 将node链接到cur的下一个节点      cur.next = node;    // 再将cur链接到node    }    return true;  }  /**  * 查找是否包含关键字 key 在单链表中  * @param key 要查找的关键字  * @return 找到key返回true，否则返回fal  */  @override  public boolean contains(int key) {    node cur = this.head;    while (cur != null) {      if (cur.data == key) {        return true;      }      cur = cur.next;    }    return fal;  }  // 找第一次出现的关键字为 key 的节点的前驱  private node archpre(int key) {    // 1. 是不是第一个节点 if(head,data == key)    node pre = this.head;    if (pre.data == key) {      // 或者 return null;      return this.head;    }    // 2. if(cur.next.data == key)    while (pre.next != null) {      if (pre.next.data == key) {        return pre;      }      pre = pre.next;    }    return null;  }  /**  * 删除第一次出现的关键字为 key 的节点  * @param key 要删除的关键字  * @return olddata  */  @override  public int remove(int key) {    int olddata = 0;    node pre = archpre(key);    // 1. 若没有找到    if (pre == null) {      // return -1;      throw new unsupportedoperationexception("没有key的前驱");    }    // 2. 找到了，并且在第一个节点    if (pre == this.head && pre.data == key){      olddata = this.head.data;      this.head = this.head.next;      return olddata;    }    // 3. 找到了，并且不在第一个节点    node delnode = pre.next; // 确定要删除的节点的位置    pre.next = delnode.next; // 让要删除的节点的前驱指向要删除的节点的后一个节点，进而删除该节点    return 0;  }  /**  * 删除所有值为 key 的节点  * @param key 要删除的节点的值  */  @override  public void removeallkey(int key) {    node pre = this.head;    node cur = this.head.next;    // 遍历一遍链表    while (cur != null) {      // 若找到了关键字，进行删除      if (cur.data == key) {        pre.next = cur.next;        cur = cur.next;      } el { // 若不是关键字，继续查看链表的下一个        pre = cur;        cur = cur.next;      }      if (this.head.data == key) {        this.head = this.head.next;      }    }  } /**  * 得到单链表的长度  * @return 单链表长度  */  @override  public int getlength() {    node cur = this.head;    int count = 0; // 节点的个数    while (cur != null) {      count++;      cur = cur.next;    }    return count;  }  /**  * 打印单链表  */  @override  public void display() {    node cur = this.head;    while (cur != null) {      system.out.print(cur.data + " ");      cur = cur.next;    }    system.out.println();  }  /**  * 清空单链表以防内存泄漏  */  @override  public void clear() {    while (this.head != null) {      node cur = this.head.next;      this.head.next = null;      this.head = cur;    }  }}

3. 测试代码

package com.github.linked.impl;public class testdemo {  public static void main(string[] args) {    //mysinglelistimpl mysinglelist = new mysinglelistimpl();    singlelisted mysinglelist = new singlelisted();    mysinglelist.addfirst(10);    mysinglelist.addfirst(20);    mysinglelist.addfirst(30);    mysinglelist.addfirst(40);    mysinglelist.addfirst(50);    system.out.println("头插：");    mysinglelist.display();    mysinglelist.addlast(100);   论文答辩陈述 mysinglelist.addlast(200);    system.out.println("尾插：");    mysinglelist.display();    system.out.println();    system.out.print("单链表的长度：");    system.out.println(mysinglelist.getlength());    system.out.println();    mysinglelist.addindex(1,15);    system.out.println("任意位置插入：");    mysinglelist.display();    system.out.println();    system.out.println("查找是否包含关键字 key 在单链表中：");    system.out.println("查找关键字125："+mysinglelist.contains(125));    system.out.println("查找关键字30："+mysinglelist.contains(30));    system.out.println();    system.out.println("删除第一次出现的关键字为 key 的节点：");    system.out.println("删除头节点50：");    mysinglelist.remove(50); //删除头节点    mysinglelist.display();    system.out.println("删除中间节点30：");    mysinglelist.remove(30); // 删除中间节点    mysinglelist.display();    system.out.println("删除尾节点200：");    mysinglelist.remove(200); // 删除尾节点    mysinglelist.display();    system.out.println();    system.out.println("删除第一次出现的关键字为 key 的节点：");    mysinglelist.addfirst(20);    mysinglelist.display();    mysinglelist.removeallkey(20);    mysinglelist.display();    system.out.println();    system.out.print("单链表的长度：");    system.out.println(mysinglelist.getlength());    system.out.println();    // 测试内存泄漏    try {      thread.sleep(1000);      system.out.println("睡醒了")普通高考报名网;    } catch (interruptedexception e) {      e.printstacktrace();    }  }}

4. 测试结果

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持www.887551.com。