JAVA数据结构之链表
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