JAVA 实现单向链表 Linked 作者：马育民 • 2022-07-02 17:05 • 阅读：10036 # 说明 单链表里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成 在java集合框架里面 `LinkedList`、`HashMap`（数组加链表）等等的底层都是用链表实现的。 ### 链表结果 [](/upload/0/0/1IX3bVNd8FSN.png) ### 添加元素 [](/upload/0/0/1IX3bVNnHkCQ.png) ### 删除 [](/upload/0/0/1IX3bVO2JUnT.png) ### 特点 - 数据元素在内存中存放的 **地址是不连续的**：单链表的结点里面还定义一个结点，它里面保存着下一个结点的内存地址，在实例化对象的时候，jvm会开辟不同内存空间，并且是不连续的。 - 添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将插入结点的next指向第一个元素的next # java ### 节点类 ``` /** * 节点类 * @author mym * */ public class Node { private Object data; private Node next; public Node(Object data) { this.data = data; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } ``` ### 链表类 ``` public class MyLinked { /** * 第一个节点 */ private Node head; /** * 链表长度，即：节点数量 */ private int size = 0; /** * 在尾部添加节点 * @param data */ public void add(Object data){ add(size,data); } /** * 插入节点 * @param index * @param data */ public void add(int index,Object data){ // 索引校验 if(index < 0){ throw new IndexOutOfBoundsException("index 不能小于 0"); } // index 可以等于 size（长度），表示插入到末尾，但不能大于size（长度） if(index > size){ throw new IndexOutOfBoundsException("index 不能大于长度，长度是： "+size); } Node node = new Node(data); if(index == 0){ // 头部插入节点 if( head == null){ // 如果链表是空，没有元素 head = node; }else{ // 如果链表不为空，有元素 node.setNext(head); head = node; } }else{ // 中间添加节点、或 尾部添加节点 Node temp = head; // 循环取出添加节点的前一个位置 for(int i = 1; i<index;i++){ temp = temp.getNext(); } Node oldNext = temp.getNext(); // 让前一个节点指向新节点 temp.setNext(node); // 新节点指向原来的下一个节点 node.setNext(oldNext); } size ++; } /** * 根据索引取出节点 * @param index * @return */ public Object get(int index){ // 索引校验 if(index < 0){ throw new IndexOutOfBoundsException("index 不能小于 0"); } if(size == 0){ throw new IndexOutOfBoundsException("长度是： "+size+"，没有元素"); } if(index >= size){ throw new IndexOutOfBoundsException("index 不能大于等于长度，长度是： "+size); } Node ret = null; if(index == 0){ // 取出第一个节点 ret = head; }else{ // 取出中间阶段 Node temp = head; // 循环指定的索引位置，取出该节点 for(int i = 0; i<index;i++){ temp = temp.getNext(); } ret = temp; } return ret.getData(); } /** * 删除指定索引的节点 * @param i * @return */ public Object remove(int index){ // 索引校验 if(index < 0){ throw new IndexOutOfBoundsException("index 不能小于 0"); } if(size == 0){ throw new IndexOutOfBoundsException("长度是： "+size+"，没有元素"); } if(index >= size){ throw new IndexOutOfBoundsException("index 不能大于等于长度，长度是： "+size); } Node ret = null; if(index == 0){ // 删除第一个节点 ret = head; // 将第一个节点的下一个节点作为第一个节点 head = head.getNext(); }else{ // 取出中间阶段 Node temp = head; // 循环，取出要删除节点的前一个节点 for(int i = 0; i<index-1;i++){ temp = temp.getNext(); } //取出要删除的节点 ret = temp.getNext(); // 取出要删除节点的下一个节点 Node next = ret.getNext(); // 让前一个节点，指向下一个节点 temp.setNext(next); } size--; return ret.getData(); } public int size(){ return size; } } ``` ### 测试类 ``` import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class TestLinked { public static void main(String[] args) { MyLinked link = new MyLinked(); link.add(0,"李雷"); link.add("韩梅梅"); link.add(0,"lucy"); link.add(2,"lili"); link.add(link.size(),"张三"); // Object obj2 = link.remove(0); // System.out.println("删除："+obj2); // // Object obj3 = link.remove(link.size()-1); // System.out.println("删除："+obj3); Object obj3 = link.remove(2); System.out.println("删除："+obj3); System.out.println("----"); // 遍历 for(int i = 0;i<link.size();i++){ Object obj = link.get(i); System.out.println(obj); } } public static void main2(String[] args) { // 测试校验 MyLinked l = new MyLinked(); l.add("李雷"); // l.add(-10, ""); // l.add(10, ""); // l.get(-10); // l.get(10); // l.get(0); // l.remove(-10); l.remove(10); } public static void main1(String[] args) { List list = new ArrayList(); // list.add("李雷"); // list.add(-1,""); // list.add(5, "韩梅梅"); //java.lang.IndexOutOfBoundsException // list.get(2); list.get(0); LinkedList ll = new LinkedList(); } } ``` #### 参考 https://blog.csdn.net/m0_51724241/article/details/124307269 https://www.javazhiyin.com/72610.html 原文出处：http://malaoshi.top/show_1IX3bVPX5UuZ.html