java实现链表

article/2025/10/12 20:36:40

一、链表定义

链表通过指针将一组零散的内存块串联在一起进行使用。
数据格式：
在这里插入图片描述
根据上面的图展示，每个内存块可以称为链条的一个“结点”，结点包含了数据和下一个结点的地址；同时有2个结点特殊：第一个结点和最后一个结点，第一个结点称为“头节点”，存储链表基地址，最后一个结点称为“尾节点”，尾节点的下一个结点为空地址 NULL。

二、链表实现定义

public class LinkList<T> {//结点定义private class Node{//数据T item;//指向下一个结点Node next;//构造器public Node(T item,Node next){this.item = item;this.next = next;}public Node(T item){this.item = item;}}//头结点private Node head;//尾结点private Node tail;//结点个数private int size;//链表定义public LinkList(){this.head = new Node(null,null);size = 0;}}

三、查找特定位置的链表结点

//查找特定位置的链表结点public Node get(int index) {if (index <0 || index >=this.size){return null;}else{Node temp = this.head;for(int i =1;i<=index;i++){temp = temp.next;}return temp;}}

四、插入链表结点

在这里插入图片描述
注意：
将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。

//在链表的第i个位置插入一个值为t数据public void insert(int index ,T data) throws Exception{if(index <0 ||index > this.size){throw new Exception("插入超出范围");}else{Node newNode = new Node(data);//在头结点插入元素if (index ==0){if(this.size >0){Node temp = head;newNode.next = temp;}head = newNode;}//在尾结点插入元素else if(index == this.size){Node temp = tail;temp.next = newNode;this.tail  = newNode;}else{//在中间插入元素Node preNode = get(index-1);Node nextNode = preNode.next;newNode.next = nextNode;preNode.next = newNode;}}this.size ++;if(size == 1){tail = head;}}

五、删除链表结点

//删除特定位置的数据public void del(int index )throws Exception{if (index <0 ||index >=this.size){throw new Exception("删除超出范围");}else{//删除头结点if (index == 0){Node temp = this.head.next;this.head = temp;}else if(index == this.size-1){    //删除尾结点Node preNode = get(index -1);this.tail = preNode;preNode.next = null;}else{//删除中间结点Node preNode = get(index -1);Node nextNode = preNode.next.next;preNode.next = nextNode;}}this.size --;}

六、整体代码

public class LinkList<T> {//结点定义private class Node{//数据T item;//指向下一个结点Node next;//构造器public Node(T item,Node next){this.item = item;this.next = next;}public Node(T item){this.item = item;}}//头结点private Node head;//尾结点private Node tail;//结点个数private int size;//链表定义public LinkList(){this.head = new Node(null,null);size = 0;}//查找特定位置的链表结点public Node get(int index) {if (index <0 || index >=this.size){return null;}else{Node temp = this.head;for(int i =1;i<=index;i++){temp = temp.next;}return temp;}}public void add(T data){Node temp = new Node(data);//链表为空时if (this.size == 0){head = temp;tail = head;}else{Node last  =  tail;last.next = temp;this.tail = temp;}this.size ++;}//在链表的第i个位置插入一个值为t数据public void insert(int index ,T data) throws Exception{if(index <0 ||index > this.size){throw new Exception("插入超出范围");}else{Node newNode = new Node(data);//在头结点插入元素if (index ==0){if(this.size >0){Node temp = head;newNode.next = temp;}head = newNode;}//在尾结点插入元素else if(index == this.size){Node temp = tail;temp.next = newNode;this.tail  = newNode;}else{//在中间插入元素Node preNode = get(index-1);Node nextNode = preNode.next;newNode.next = nextNode;preNode.next = newNode;}}this.size ++;if(size == 1){tail = head;}}//删除特定位置的数据public void del(int index )throws Exception{if (index <0 ||index >=this.size){throw new Exception("删除超出范围");}else{//删除头结点if (index == 0){Node temp = this.head.next;this.head = temp;}else if(index == this.size-1){    //删除尾结点Node preNode = get(index -1);this.tail = preNode;preNode.next = null;}else{//删除中间结点Node preNode = get(index -1);Node nextNode = preNode.next.next;preNode.next = nextNode;}}this.size --;}//移除末尾元素,并返回对应数据public T remove() throws Exception{if (this.size ==0){throw new Exception("链表为空，无法移除");}//只有一个元素，移除后为空if (this.size == 1){T data = this.head.item;this.head = null;this.tail = this.head;this.size --;return data;}else{Node preNode = get(this.size-2);T data  = this.tail.item;preNode.next = null;this.tail = preNode;this.size --;return data;}}//删除特定元素的第一个位置public boolean deleteData(T data){boolean flag = false;if(this.size == 0){return flag;}else{Node curNode = this.head;//元素位于第一个结点if (curNode.item == data){Node nextNode = curNode.next;head = nextNode;flag = true;//当前列表只有一个结点if (this.size ==1){tail = head;}this.size --;}else {while (curNode != null) {Node nextNode = curNode.next;if (nextNode != null && nextNode.item == data) {//删除元素为尾结点if (nextNode.next ==null){this.tail = curNode;curNode.next = null;}else{//删除结点为中间结点Node temp = curNode.next.next;curNode.next = temp;}flag = true;this.size --;break;}curNode = curNode.next;}}}return flag;}public void printLinkList(){if(this.size ==0){System.out.println("链表为空");}else {Node temp = head;System.out.print("目前的列表，头结点：" + head.item + ",尾结点:" + tail.item + ",整体：");while (temp != null) {System.out.print(temp.item + ",");temp = temp.next;}System.out.println();}}public static void main(String args[]) throws Exception {LinkList linkList = new LinkList();linkList.add("2");linkList.del(0);linkList.printLinkList();linkList.insert(0,"a");System.out.println("删除的元素为："+linkList.remove());linkList.insert(0,"2");linkList.insert(1,"3");linkList.add("3");linkList.printLinkList();linkList.del(1);linkList.printLinkList();linkList.insert(1,"1");linkList.insert(0,"0");linkList.insert(2,"0");linkList.del(2);linkList.printLinkList();linkList.deleteData(3);linkList.printLinkList();}}