阅读 360

数据结构学习与应用-链表

链表

概念

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

存储结构

单向链表是一种线性表,实际上是由节点(Node)组成的,每一个链表都包含多个节点,节点又包含两个部分,一个是数据域 data(储存节点含有的信息),一个是引用域 next(储存下一个节点或者上一个节点的地址)。其数据在内存中存储是不连续的,它存储的数据分散在内存中,每个结点只能也只有它能知道下一个结点的存储位置。由 N 个节点(Node)组成单向链表,每一个 Node 记录本Node的数据及下一个 Node。向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。

在这里插入图片描述

节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。

在这里插入图片描述

特点

  1. 获取数据麻烦,需要遍历查找,比数组慢。O(n)
  2. 方便插入、删除。O(1)

常用操作

1.节点Node

public class LJLinkNode<T> {

	public LJLinkNode next;
	public T data;

	public LJLinkNode() {
		this.next = null;
		this.data = null;
	}

	public LJLinkNode(T data) {
		this.data = data;
		this.next = null;
	}

}
复制代码

2.创建链表 在链表中有一个头指针,它的next域用于指示链表第一个节点。

// 链表头的引用 ,类似于头指针
public LJLinkNode<T> headNode = new LJLinkNode<T>();
复制代码

3.插入 在链表中插入一个节点,有尾插法,即在链表的尾部插入一个节点。首先需要判断当前的链表是否是空链表,是的话就在头节点进行插入,不是的话需要遍历链表,到尾部进行插入节点:

    /**
	 * 插入一条数据
	 * 
	 * @param value
	 */
	public void add(T value) {
		// 如果是头节点的话,在next指针域中插入
		if (headNode.next == null) {
			headNode.next = new LJLinkNode<>(value);
			return;
		}

		LJLinkNode<T> tempNode = headNode;
		while (tempNode.next != null) {
			tempNode = tempNode.next;
		}
		tempNode.next = new LJLinkNode<>(value);
	}
复制代码

4.删除一个节点

删除一个指定位置上面的节点,首先需要遍历到那个位置,然后将当前节点的前一个节点的next指向当前节点的后一个节点,即跳过当前节点。因为当前节点无法获取到它,因此就相当于删除了。

	/**
	 * 删除指定index的一个节点
	 * 
	 * @param data
	 */
	public boolean del(int index) {

		// index下标越界
		if (index < 0 || index > length()) {
			return false;
		}

		// 删除头节点
		if (index == 1) {
			headNode = headNode.next;
			return true;
		}

		LJLinkNode<T> preNode = headNode;
		LJLinkNode<T> curNode = preNode.next;
		int i = 2;
		while (curNode != null) {
			if (i == index) {
				// 指向删除节点的后一个节点
				preNode.next = curNode.next;
				break;
			}
			preNode = curNode;
			curNode = preNode.next;
			i++;
		}
		return true;
	}
复制代码

5.链表长度

链表长度很好理解,遍历链表即可:

	/**
	 * 链表长度
	 * 
	 * @return
	 */
	public int length() {
		int i = 0;
		LJLinkNode<T> tempLinkNode = headNode;
		while (tempLinkNode.next != null) {
			i++;
			tempLinkNode = tempLinkNode.next;
		}
		return i;
	}
复制代码

6.获取指定位置上的链表节点

获取到指定位置上的节点的话,需要遍历到当前位置,然后获取它的节点:

	/**
	 * 获取第index的节点
	 * 
	 * @param index
	 * @return
	 */
	public LJLinkNode<T> getIndexLinkNode(int index) {
		if (index < 0 || index > length()) {
			return null;
		}
		LJLinkNode<T> tempNode = headNode;
		int i = 0;
		while (tempNode != null) {
			if (index == i) {
				break;
			}
			i++;
			tempNode = tempNode.next;
		}
		return tempNode;
	}
复制代码

以上便是链表的基本操作,插入,删除等。在面试过程中还会有其他的算法,我们拿出几个来简单说明一下链表的算法应用。

算法应用

1.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/me…

在这里插入图片描述

关注下面的标签,发现更多相似文章
评论