JAVA数据结构之链表
程序员文章站
2022-03-03 08:03:53
1、单链表的数据结构单链表中的数据是以结点的形式存在，每一个结点是由数据元素（数据域）和下一个结点的存储的位置（指针域）组成。单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，而数组的数据元素存放的地址在内存空间中是连续的。具体的数据模型用下图大概描述一下。2、单链表的优缺点优点：插入删除速度快、内存利用率高，不会浪费内存、大小没有固定，拓展很灵活由于链表的节点在内存中可以存在任何地方、不要求连续，且每个节点中都存储着下一节点的内存地址。如果需要新插....
1、单链表的数据结构
单链表中的数据是以结点的形式存在，每一个结点是由数据元素（数据域）和下一个结点的存储的位置（指针域）组成。单链表与数组相比的最大差别是：单链表的数据元素存放在内存空间的地址是不连续的，而数组的数据元素存放的地址在内存空间中是连续的。具体的数据模型用下图大概描述一下。
2、单链表的优缺点
优点：
插入删除速度快、内存利用率高，不会浪费内存、大小没有固定，拓展很灵活
由于链表的节点在内存中可以存在任何地方、不要求连续，且每个节点中都存储着下一节点的内存地址。如果需要新插入一个新节点（数据），只需要把此节点的内存地址指向下一节点，上一节点的内存地址指向本节点就OK了，其余节点都不用发生改变，所以插入删除速度快。不像数组一样增加、删除数据后其他的元素的下标都得发生改变。
缺点：
不可以进行随机查询
这个由链表的数据结构决定的，查询某个节点的数据都必须在head（头节点）依次指向下一节点，直到找到我们需要的数据节点。这一点不像数组一样可以根据数组下标直接进行查询。
3、单链表的简单实现
在这里就使用代码简单的实现下单链表的数据结构，并实现增删改查。
新建一个节点类，用来存储每个节点的数据
public class Node <T>{
//数据域
public T t;
//指针域
public Node next;
public Node(T t,Node next){
this.t = t;
this.next = next;
}
public Node(T t){
this(t,null);
}
}新建链表类，声明增删改查方法
1、在链表头部新增节点方法
public class LinkList<T> {
private Node head; //头结点
private int size; //链表元素个数
//构造函数
public LinkList(){
this.head = null;
this.size = 0;
}
/**
* 往链表头部插入值
* @param t
*/
public void addFirst(T t) {
Node node = new Node(t); //节点对象
node.next = this.head;
this.head = node;
this.size++;
}
/**
* java类的默认继承方法，继承于object类。
*/
public String toString() {
StringBuffer sb = new StringBuffer();
Node cur = this.head;
while(cur != null){
sb.append(cur.t+"=>");
cur = cur.next;
}
sb.append("NULL");
return sb.toString();
}
}在链表的头部新增节点，具体操作是把新节点的next指向当前头结点，更新this.head为新增的节点，节点数量加一。具体如下图：
测试方法：
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkList<String> linklist = new LinkList();
String[] strArray = new String[6];
strArray[0] = "one";
strArray[1] = "two";
strArray[2] = "three";
strArray[3] = "four";
strArray[4] = "five";
strArray[5] = "six";
for(String str : strArray) {
linklist.addFirst(str);
System.out.println(linklist);
}
}执行main方法
2、在链表根据位置插入数据
具体代码如下：
/**
* 往链表中间插入值
* @param index
* @param t
*/
public void add(int index,T t) {
//当index值小于零或者大于链表长度时，抛出异常
if (index <0 || index > this.size){
throw new IllegalArgumentException("index is error");
}
//当index为零的时候向链表头部插入一个值
if (index == 0){
this.addFirst(t);
}
//获取当前链表的头元素（第一个值）
Node preNode = this.head;
//找到要插入节点的前一个节点
for(int i=0;i<index-1;i++) {
preNode = preNode.next;
}
Node cruNode = new Node(t);
//要插入的节点的下一个节点指向preNode节点的下一个节点
cruNode.next = preNode.next;
//preNode的下一个节点指向要插入节点node
preNode.next = cruNode;
this.size++;
}原理图形表达：
测试代码main如下：
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkList<String> linklist = new LinkList();
String[] strArray = new String[6];
strArray[0] = "one";
strArray[1] = "two";
strArray[2] = "three";
strArray[3] = "four";
strArray[4] = "five";
strArray[5] = "six";
for(String str : strArray) {
linklist.addFirst(str);
System.out.println(linklist);
}
linklist.add(3, "23");
System.out.println(linklist);
linklist.add(3, "45");
System.out.println(linklist);
}测试结果如下：
3、查询方法
//链表中是否包含某个元素
public boolean contains(T t){
Node cur = this.head;
while(cur != null){
if(cur.t.equals(t)){
return true;
}
else {
cur = cur.next;
}
}
return false;
}根据方法传入的值从链表的头部进行遍历，如果找到了return结果true，找不到就return结果false。
测试代码：
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkList<String> linklist = new LinkList();
String[] strArray = new String[6];
strArray[0] = "one";
strArray[1] = "two";
strArray[2] = "three";
strArray[3] = "four";
strArray[4] = "five";
strArray[5] = "six";
for(String str : strArray) {
linklist.addFirst(str);
System.out.println(linklist);
}
linklist.add(3, "23");
System.out.println(linklist);
linklist.add(3, "45");
System.out.println(linklist);
System.out.println(linklist.contains("four"));
System.out.println(linklist.contains("ten"));
}演示结果：
4、删除方法
public void remove(T t) {
if(this.head ==null) {
System.out.println("链表中无数据，不可进行删除！！");
}else {
//如果要删除的元素跟链表头部的元素相同，就删除头部（把头元素的指向的元素设为头元素）
if(head.t.equals(t)) {
head = head.next;
this.size--;
}else {
//获取当前节点为头部节点
Node cur = this.head;
//一直循环遍历链表到最后
while(cur.next != null) {
//当前元素的下一个元素为要删除的值时，那就把当前元素下一个元素的下一个元素 设为 当前元素的下一个元素
if(cur.next.t.equals(t)) {
cur.next = cur.next.next;
}else {
cur = cur.next;
}
}
}
}
}原理图形表达：
测试代码：
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkList<String> linklist = new LinkList();
String[] strArray = new String[6];
strArray[0] = "one";
strArray[1] = "two";
strArray[2] = "three";
strArray[3] = "four";
strArray[4] = "five";
strArray[5] = "six";
for(String str : strArray) {
linklist.addFirst(str);
System.out.println(linklist);
}
linklist.add(3, "23");
System.out.println(linklist);
linklist.add(3, "45");
System.out.println(linklist);
System.out.println(linklist.contains("four"));
System.out.println(linklist.contains("ten"));
linklist.remove("45");
System.out.println(linklist);
}测试的结果：
到这就简单演示了单链表的数据结构，深入研究还是看一下java的LinkedList。
本文地址：https://blog.csdn.net/lw1124052197/article/details/108859915