欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JAVA数据结构之链表

程序员文章站 2022-06-14 22:13:01
1、单链表的数据结构单链表中的数据是以结点的形式存在,每一个结点是由数据元素(数据域)和下一个结点的存储的位置(指针域)组成。单链表与数组相比的最大差别是:单链表的数据元素存放在内存空间的地址是不连续的,而数组的数据元素存放的地址在内存空间中是连续的。具体的数据模型用下图大概描述一下。2、单链表的优缺点优点:插入删除速度快、内存利用率高,不会浪费内存、大小没有固定,拓展很灵活由于链表的节点在内存中可以存在任何地方、不要求连续,且每个节点中都存储着下一节点的内存地址。如果需要新插....

1、单链表的数据结构

单链表中的数据是以结点的形式存在,每一个结点是由数据元素(数据域)和下一个结点的存储的位置(指针域)组成。单链表与数组相比的最大差别是:单链表的数据元素存放在内存空间的地址是不连续的,而数组的数据元素存放的地址在内存空间中是连续的。具体的数据模型用下图大概描述一下。

JAVA数据结构之链表


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为新增的节点,节点数量加一。具体如下图:

JAVA数据结构之链表

测试方法:

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方法

JAVA数据结构之链表

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++;
	}

原理图形表达:

JAVA数据结构之链表

测试代码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);
		

	}

测试结果如下:

JAVA数据结构之链表

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"));
	
	}

演示结果:

JAVA数据结构之链表

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;
					}
				}
				
			}
			
		}
		
	}

原理图形表达:

JAVA数据结构之链表

测试代码:

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

到这就简单演示了单链表的数据结构,深入研究还是看一下java的LinkedList。

本文地址:https://blog.csdn.net/lw1124052197/article/details/108859915