为什么那么多人建网站做博客,免费一天赚500元游戏,重庆森林讲的什么内容,安卓盒子做网站一、概述 链表是一种常见的数据结构#xff0c;用于存储一系列具有相同类型的数据元素。它由多个节点组成#xff0c;每个节点包含一个数据元素和一个指向下一个节点的指针。 链表与数组不同#xff0c;它的节点在内存中不是连续存储的#xff0c;而是通过每个节点中的指针…一、概述 链表是一种常见的数据结构用于存储一系列具有相同类型的数据元素。它由多个节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。 链表与数组不同它的节点在内存中不是连续存储的而是通过每个节点中的指针链接在一起。这使得链表的插入和删除操作更加高效但访问任意节点时需要遍历链表因此访问操作的效率较低。 链表通常具有一个头节点用于指向链表的第一个节点。如果链表为空则头节点为空。在链表末尾最后一个节点的指针通常为NULL表示链表的结束。 链表有多种类型包括单链表、双向链表和循环链表。单链表只有一个指向下一个节点的指针双向链表有两个指针一个指向前一个节点一个指向后一个节点而循环链表的最后一个节点的指针指向链表的头节点。 链表的优点是插入和删除操作的高效性特别是在链表的中间位置。链表的缺点是访问操作的效率较低因为需要遍历链表。另外由于链表的节点需要存储额外的指针所以链表比数组占用更多的内存空间。 总之链表是一种灵活且常用的数据结构在许多应用中都有广泛的应用。 在Java中因为取消了指针所以我们只能用内部类的方式来处理节点和节点之间的关联关系。
二、链表的特点 链表是真正的动态数据结构不同于数组的扩容和缩容链表本身通过next来连接下一个节点不会存在内存浪费和溢出的情况同时链表也是最简单的数据结构掌握链表可以帮助我们学习更复杂的数据结构如图和树。学习链表也有助于更深入的理解引用和递归。 在Java中本身也给我们提供了一种链表LinkedList它是一个泛型类实现了栈和队列等一系列接口方法在学习算法和开发中会经常用到十分的灵活好用。
三、链表的实现 为了更深刻的理解链表这种数据结构我们将自己编写一个链表代码如下供读者参考
代码实现
public class LinkedListT {//节点class NodeT{//数据域T data;//指针域NodeT next;public Node(T data) {this.data data;}public Node(T data, NodeT next) {this.data data;this.next next;}}//链表的头节点private NodeT Head;//链表的长度private int length;//初始化public LinkedList(){//创建头节点下一个为首元节点this.Head new NodeT(null,null);this.length 0;}//判断链表是否为空public boolean isEmpty(){return getLength()0;}//获得链表长度public int getLength(){return this.length;}//添加节点//头插法public boolean addFirst(T data){return add(data,1);}//在第几个位置插入元素public boolean add(T data,int index){if(index getLength()1 || index 1) return false;index--;NodeT tempNode this.Head;int index_ 0;while (tempNode!nullindex!index_){tempNode tempNode.next;index_;}tempNode.next new Node(data,tempNode.next);this.length;return true;}//尾插法public boolean addLast(T data){return add(data,getLength()1);}//遍历这里借用Object.toString的方法将其进行重写Overridepublic String toString() {NodeT tempNode this.Head.next;StringBuilder builder new StringBuilder();while (tempNode!null){builder.append(tempNode.data -);tempNode tempNode.next;}builder.append(NULL);return builder.toString();}//查找元素是否存在public boolean isHave(T data){NodeT tNode this.Head.next;while (tNode!null){if(tNode.data.equals(data)) return true;tNode tNode.next;}return false;}//获取指定位置元素//获取首元节点元素public T getFirst(){return get(1);}//获取指定位置元素public T get(int index){if(index getLength() || index 1) return null;index--;NodeT tempNode this.Head;int index_ 0;while (tempNode!nullindex!index_){tempNode tempNode.next;index_;}return tempNode.next.data;}//获取尾节点元素public T getLast(){return get(getLength());}//删除节点//删除头节点public T removeFirst(){return remove(1);}//删除指定位置节点public T remove(int index){if(index getLength() || index 1) return null;index--;NodeT tempNode this.Head;int index_ 0;while (tempNode!nullindex!index_){tempNode tempNode.next;index_;}T res tempNode.next.data;tempNode.next tempNode.next.next;this.length--;return res;}//删除尾节点public T removeLast(){return remove(getLength());}//删除第一个指定元素的节点public boolean remove(T data){NodeT tempNode this.Head;while (tempNode.next!null){if(tempNode.next.data.equals(data)){tempNode.next tempNode.next.next;this.length--;return true;}tempNode tempNode.next;}return false;}//删除链表中所有是这个元素的节点public int removeAll(T data){int count 0;while (remove(data)) count;return count;}//修改指定位置的值public boolean set(T data,int index){remove(index);return add(data,index);}//使用递归的方式删除链表元素public void remove_all_by_recursion(T value){this.Head.next recursion_remove(value,this.Head.next);}private Node recursion_remove(T value,Node node){//递归终止条件if(nodenull) return null;//递归操作if(node.data.equals(value)){this.length--;return node.next;}else {node.next recursion_remove(value,node.next);return node;}}
}
测试链表
import java.util.Random;public class testMyLinked {public static void main(String[] args) {Random random new Random();LinkedListInteger linkedList new LinkedList();System.out.println(linkedList.getFirst());System.out.println(linkedList.getLast());for(int i 0;i 10;i){linkedList.addLast(random.nextInt(10));System.out.println(linkedList.toString());}linkedList.add(666,5);for(int i 0;i 10;i){linkedList.addFirst(random.nextInt(10));System.out.println(linkedList.toString());}System.out.println(linkedList.isHave(666));System.out.println(linkedList.add(1145, 10));System.out.println(linkedList.isHave(114));System.out.println(linkedList.get(15));System.out.println(linkedList.getFirst());System.out.println(linkedList.getLast());System.out.println(linkedList.remove(16));System.out.println(linkedList.toString());System.out.println(linkedList.removeFirst());System.out.println(linkedList.removeLast());System.out.println(linkedList.toString());System.out.println(linkedList.remove(new Integer(1145)));System.out.println(linkedList.toString());System.out.println(linkedList.removeAll(new Integer(6)));System.out.println(linkedList.toString());System.out.println(linkedList.set(1919, 6));System.out.println(linkedList.toString());linkedList.remove_all_by_recursion(4);System.out.println(linkedList.toString());}
}
输出结果
