数据结构之链表（Java实现）

🍉概述

🍉单链表

🍊简介

🍋存储示意图

🍌单链表的基本实现（类设计）

类名：

• LinkList<T>：可以根据自己的喜好自定义，T是泛型，存入的元素类型，假设创建对象时，设置LinkList<String>，表示该顺序表只能存放String类型的元素

结点类：

• private class Node ：结点，方便将各个结点连接成链表

	private class Node{
		//	存储数据
		T item;
		//	下一个结点
		Node next;
		public Node(T item, Node next) {
			this.item = item;
			this.next = next;
		}
		public Node() {};
	}

成员变量：

• 头结点：private Node head;
• 链表长度：private int N;

构造方法：

• public LinkList()：初始化头结点指向null，初始化长度为0

	public LinkList(){
		//	初始化头结点
		this.head = new Node();
		//	初始化元素个数
		this.N = 0;
	}

成员方法：

• public void clear()：清空链表（直接让头结点指向null，长度重置为0）

	public void clear() {
		this.head = null;
		this.N = 0;
	}

• public int length()：获取链表长度（返回N即可）

	public int length() {
		return N;
	}

• public boolean isEmpty()：链表是否为空（判断N是否为0即可）

	public boolean isEmpty() {
		return N == 0;
	}

• public T get(int i)：获取指定位置的元素（用一个临时结点指向头结点，不断的让临时结点指向它的下一个结点）

	public T get(int i) {
		//	通过循环，从头结点开始往后查找
		Node node = head;
		for (int j = 0; j <= i; j++) {
			node = node.next;
		}
		return node.item;
	}

• public void insert(T t)：向链表添加元素

	public void insert(T t) {
		//找到当前最后一个结点
		Node last = head;
		while(last.next!=null)
			last = last.next;
		//创建新结点，保存元素t
		Node now = new Node(t,null);
		//让当前最后一个结点指向新结点
		last.next = now;
		//	让元素个数加一
		this.N++;
	}

• public void insert(int i, T t)：指定位置插入元素（找到前一个结点和 i 位置结点，前一个结点指向新结点，新节点指向 i 位置结点完成插入）

	public void insert(int i, T t) {
		Node pre = head;
		//找到i位置的前一个结点
		for (int j = 0; j < i; j++) {
			pre = pre.next;
		}
		//找到i位置的结点
		Node cur = pre.next;
		//创建新结点，前一结点指向新结点，新结点指向原来i位置的结点
		Node now = new Node(t, cur);
		pre.next = now;
		//元素个数加一
		this.N++;
	}

• public T remove(int i)：删除指定位置元素（找到 i 位置前一个和后一个结点，直接让前一个指向后一个结点）

	public T remove(int i) {
		//找到i位置前一个结点
		Node pre = head;
		for (int j = 0; j < i; j++) {
			head = head.next;
		}
		//找到i位置的结点并保存
		Node cur = pre.next;
		//找到i位置下一个结点
		Node next = cur.next;
		//前一个结点指向下一个结点
		pre.next = next;
		//元素个数减一
		this.N--;
		return cur.item;
	}

• public int indexOf(T t)：查找指定元素第一次出现的位置

	public int indexOf(T t) {
		//	从头开始依次查找每一个结点，取出item，和t比较，如果相同则找到了
		Node now = head;
		for (int i = 0; now.next!= null; i++) {
			now = now.next;
			if (now.item==t) {
				return i;
			}
		}//找不到就返回-1
		return -1;
	}

完整代码：

public class LinkList<T> {
	//	记录头结点  
	private Node head;
	//	记录链表的长度
	private int N;
	//	结点类
	private class Node{
		//	存储数据
		T item;
		//	下一个结点
		Node next;
		public Node(T item, Node next) {
			this.item = item;
			this.next = next;
		}
		public Node() {};
	}
	public LinkList(){
		//	初始化头结点
		this.head = new Node();
		//	初始化元素个数
		this.N = 0;
	}
	//	清空链表
	public void clear() {
		this.head = null;
		this.N = 0;
	}
	//	获取链表的长度
	public int length() {
		return N;
	}
	//判断链表是否为空
	public boolean isEmpty() {
		return N == 0;
	}
	//获取指定位置i处的元素
	public T get(int i) {
		//	通过循环，从头结点开始往后查找
		Node node = head;
		for (int j = 0; j <= i; j++) {
			node = node.next;
		}
		return node.item;
	}
	//向链表中添加元素t
	public void insert(T t) {
		//找到当前最后一个结点
		Node last = head;
		while(last.next!=null)
			last = last.next;
		//创建新结点，保存元素t
		Node now = new Node(t,null);
		//让当前最后一个结点指向新结点
		last.next = now;
		//	让元素个数加一
		this.N++;
	}
	//向指定位置i处添加元素t
	public void insert(int i, T t) {
		Node pre = head;
		//找到i位置的前一个结点
		for (int j = 0; j < i; j++) {
			pre = pre.next;
		}
		//找到i位置的结点
		Node cur = pre.next;
		//创建新结点，前一结点指向新结点，新结点指向原来i位置的结点
		Node now = new Node(t, cur);
		pre.next = now;
		//元素个数加一
		this.N++;
	}
	//删除指定位置i的元素，返回被删除的元素
	public T remove(int i) {
		//找到i位置前一个结点
		Node pre = head;
		for (int j = 0; j < i; j++) {
			head = head.next;
		}
		//找到i位置的结点并保存
		Node cur = pre.next;
		//找到i位置下一个结点
		Node next = cur.next;
		//前一个结点指向下一个结点
		pre.next = next;
		//元素个数减一
		this.N--;
		return cur.item;
	}
	//查找元素i在链表中第一次出现的位置
	public int indexOf(T t) {
		//	从头开始依次查找每一个结点，取出item，和t比较，如果相同则找到了
		Node now = head;
		for (int i = 0; now.next!= null; i++) {
			now = now.next;
			if (now.item==t) {
				return i;
			}
		}
		return -1;
	}
}

简单测试代码：

public class LinkListTest {
	public static void main(String[] args) {
		//	创建单向链表对象
		LinkList<String> s1 = new LinkList<>();
 		//	测试插入
		s1.insert("姚明");
		s1.insert("科比");
		s1.insert("麦迪");
		s1.insert(1,"詹姆斯");
		for (int i = 0; i < s1.length(); i++) {
			System.out.println(s1.get(i));
		}
		System.out.println("-----------------------------");
		//	测试获取
		String getres = s1.get(1);
		System.out.println("获取索引1处的结果为：" + getres);
		//	测试删除
		String removeRes = s1.remove(0);
		System.out.println("删除的元素为："+removeRes+"\t删除后长度为："+s1.length());
		//测试返回元素第一次出现的索引
		System.out.println("麦迪第一次出现的索引为："+s1.indexOf("麦迪"));
		//	测试清空
		s1.clear();
		System.out.println("清空后链表中元素的个数为："+s1.length());
	}
}

🍉双链表

🍊简介

双链表也叫双向链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

🍋存储示意图

🍌双链表的基本实现（类设计）

类名：

• TwoWayLinkList<T>：可以自定义，T是泛型，存入的元素类型

结点类：

• private class Node：前后指针和存储元素

	private class Node{
		public T item;
		public Node pre;//前一个结点
		public Node next;//后一个结点
		public Node(T item, Node pre, Node next) {//构造方法
			this.item = item;
			this.pre = pre;
			this.next = next;
		}
	}

成员变量：

• 头结点：private Node head;
• 尾结点：private Node last;
• 链表长度：private int N;

构造方法：

• public TwoWayLinkList()：初始化头、尾结点指向null，初始链表长度为0

	public TwoWayLinkList() {
		//初始化头结点和尾结点
		this.head = new Node(null,null,null);
		this.last = null;
		//初始化元素个数
		this.N = 0;
	}

成员方法：

• public void clear()：清空链表（头、尾结点置空，链表长度置为0）

	public void clear() {
		this.head.next = null;
		this.last = null;
		this.N = 0;
	}

• public int length()：获取链表长度

	public int length() {
		return this.N;
	}

• public boolean isEmpty()：判断链表是否为空

	public boolean isEmpty() {
		return N == 0;
	}

• public T getFirst()：获取第一个元素

	public T getFirst() {
		if (isEmpty()) {
			return null;
		}
		return head.next.item;
	}

• public T getLast()：获取最后一个元素

	public T getLast() {
		if (isEmpty()) {
			return null;
		}
		return last.item;
	}

• public void insert(T t)：向链表插入元素

	public void insert(T t) {
		//如果链表为空
		if (isEmpty()) {
			//创建新结点，pre指向头结点
			Node newNode = new Node(t,head,null);
			//让新结点称为尾结点
			last = newNode;
			//让头结点下一个结点指向尾结点
			head.next = last;
		}else {//如果不为空
			//创建新结点
			Node newNode = new Node(t,last,null);
			//让当前尾结点指向新结点
			last.next = newNode;
			//让新结点成为尾结点
			last = newNode;
		}
		//元素个数加一
		this.N++;
	}

• public void insert(int i, T t)：指定位置插入元素（与单链表）

	public void insert(int i, T t) {
		//找到i位置的前一个结点
		Node pre = head;
		for (int j = 0; j < i; j++) {
			pre = pre.next;
		}
		//找到i位置的结点
		Node cur = pre.next;
		//创建新结点，让其pre指向前一个结点，next指向i位置结点
		Node newNode = new Node(t,pre,cur);
		//让前一结点的next变为新结点
		pre.next = newNode;
		//让i位置的pre变为新结点
		cur.pre = newNode;
		//元素个数加一
		this.N++;
	}

• public T get(int i)：获取指定位置元素

• public int indexOf(T t)：获取指定元素第一次出现的索引
  （这两个方法跟单链表的一样，就不写出来了）

• public T remove(int i)：删除指定位置元素并返回

	public T remove(int i) {
		//找到前一个结点
		Node pre = head;
		for (int j = 0; j < i; j++) {
			pre = pre.next;
		}
		//找到i位置的下一个结点
		Node cur = pre.next;
		//找到下一个结点
		Node nextNode = cur.next;
		//让前一个结点的next指向下一个结点
		pre.next = nextNode;
		//让下一个结点的pre指向前一个结点
		nextNode.pre = pre;
		//元素个数减一
		this.N--;
		return cur.item;
	}

完整代码：

public class TwoWayLinkList<T> {
	//首结点
	private Node head;
	//尾结点
	private Node last;
	//链表长度
	private int N;
	//结点类
	private class Node{
		public T item;
		public Node pre;
		public Node next;
		public Node(T item, Node pre, Node next) {
			this.item = item;
			this.pre = pre;
			this.next = next;
		}
	}
	public TwoWayLinkList() {
		//初始化头结点和尾结点
		this.head = new Node(null,null,null);
		this.last = null;
		//初始化元素个数
		this.N = 0;
	}
	//清空链表
	public void clear() {
		this.head.next = null;
		this.last = null;
		this.N = 0;
	}
	//获取链表长度
	public int length() {
		return this.N;
	}
	//判断链表是否为空
	public boolean isEmpty() {
		return N == 0;
	}
	//获取第一个元素
	public T getFirst() {
		if (isEmpty()) {
			return null;
		}
		return head.next.item;
	}
	//获取最后一个元素
	public T getLast() {
		if (isEmpty()) {
			return null;
		}
		return last.item;
	}
	//插入元素t
	public void insert(T t) {
		//如果链表为空
		if (isEmpty()) {
			//创建新结点
			Node newNode = new Node(t,head,null);
			//让新结点称为尾结点
			last = newNode;
			//让头结点指向尾结点
			head.next = last;
		}else {//如果不为空
			//创建新结点
			Node newNode = new Node(t,last,null);
			//让当前尾结点指向新结点
			last.next = newNode;
			//让新结点成为尾结点
			last = newNode;
		}
		//元素个数加一
		this.N++;
	}
	//指定位置插入元素t
	public void insert(int i, T t) {
		//找到i位置的前一个结点
		Node pre = head;
		for (int j = 0; j < i; j++) {
			pre = pre.next;
		}
		//找到i位置的结点
		Node cur = pre.next;
		//创建新结点
		Node newNode = new Node(t,pre,cur);
		//让前一结点的next变为新结点
		pre.next = newNode;
		//让i位置的前一结点变为新结点
		cur.pre = newNode;
		//元素个数加一
		this.N++;
	}
	//获取指定位置的元素
	public T get(int i) {
		Node now = head.next;
		for (int j = 0; j < i; j++) {
			now = now.next;
		}
		return now.item;
	}
	//找到第一次出现t的位置
	public int indexOf(T t) {
		Node now = head;
		for (int i = 0; now.next != null; i++) {
			now = now.next;
			if (now.item.equals(t)) {
				return i;
			}
		}
		return -1;
	}
	//删除i处的元素，并返回其元素
	public T remove(int i) {
		//找到前一个结点
		Node pre = head;
		for (int j = 0; j < i; j++) {
			pre = pre.next;
		}
		//找到i位置的下一个结点
		Node cur = pre.next;
		//找到下一个结点
		Node nextNode = cur.next;
		//让前一个结点的next指向下一个结点
		pre.next = nextNode;
		//让下一个结点的pre指向前一个结点
		nextNode.pre = pre;
		//元素个数减一
		this.N--;
		return cur.item;
	}
}

测试可以直接模仿单链表那里的测试。

觉得有帮助的小伙伴可以给博主点个赞👀，你的点赞就是对博主的最大支持😜