您的位置: 首页  >  文章  >  数据结构与算法_02【动态链表】

数据结构与算法_02【动态链表】

分类: 文章 • 2025-05-22 12:37:16

1.动态链表——线性表的链式存储结构
为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素a1来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。
指针域中存储的信息称为指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）
n个结点链接成一个链表，即为线性表的链式存储结构，因此链表的每个结点只包含一个指针域，所以叫做单链表。
头指针
头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
头指针具有标识作用，所以常用头指针冠以链表的名字
无论链表是否为空，头指针均不为空。头指针是链表的必要元素
数据结构与算法_02【动态链表】
头结点
头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义
有了头结点，对在第一个元素结点前插入结点和删除第一个结点，其操作与其它结点的操作就统一了
头结点不一定是链表必须要素
数据结构与算法_02【动态链表】
LinkedList 单向链表类定义
1.定义类

public class LinkedList<E> implements List<E>

2.定义成员变量

private Node head; //单链表中头结点的头指针
private Node rear; //单链表中尾结点的尾指针
private int size; //单链表中元素的个数
private class Node{ //内部类，定义结点类 包含所存储的元素e和下一个结点的地址next
E e;
Node next;

3.定义构造函数

public LinkedList() //默认创建一个空链表（头结点不为空，头指针指向头结点，头结点next为空，e不存储任何数据）
public LinkedList(E[] datas) //将一个指定数组datas初始化为一个单链表

4.定义成员函数
实现List接口函数

public String toString()//返回该单链表的字符串形式


package 数据结构与算法;

import 数据结构与算法.List;
//动态链表实现线性表——元素与元素之间的关系是一个方向的吧 -单向链表
public class LinkedList<E> implements List<E>{
	private Node head;	//头指针
	private Node rear;	//尾指针
	private int size;	//元素个数
	public LinkedList(){
		head=new Node();	//创建虚拟头结点
		rear=head;
		size=0;
	}
	private class Node{
		E data;
		Node next;
		public Node(){
			this(null,null);
		}
		public Node(E data){
			this(data,null);
		}
		public Node(E data,Node next){
			this.data=data;
			this.next=next;
		}
	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size==0;
	}

	@Override
	public void add(int index, E e) {
		if(index<0||index>size){
			throw new IllegalArgumentException("角标非法！");
		}
		Node n=new Node(e);//封装节点
		if(index==0){//头插
			n.next=head.next;
			head.next=n;
			if(isEmpty()){//第一次添加元素 要更新尾指针
				rear=n;
			}
		}else if(index==size){//尾插
			n.next=rear.next;
			rear.next=n;
			rear=n;
		}else{//中间插
			Node p=head;
			for(int i=0;i<index;i++){
				p=p.next;
			}
			n.next=p.next;
			p.next=n;
		}
		size++;
	}

	@Override
	public void addFirst(E e) {
		add(0,e);
	}

	@Override
	public void addLast(E e) {
		add(size,e);
	}

	@Override
	public E get(int index) {
		if(index<0||index>=size){
			throw new IllegalArgumentException("角标非法！");
		}
		if(index==0){//表头
			return head.next.data;
		}else if(index==size-1){//表尾
			return rear.data;
		}else{//中间
			Node p=head;
			for(int i=0;i<=index;i++){
				p=p.next;
			}
			return p.data;
		}
	}

	@Override
	public E getFirst() {
		return get(0);
	}

	@Override
	public E getLast() {
		return get(size-1);
	}

	@Override
	public E remove(int index) {
		if(index<0||index>=size){
			throw new IllegalArgumentException("角标非法！");
		}
		E res=null;
		if(index==0){//删头
			Node n=head.next;
			res=n.data;
			head.next=n.next;
			n=null;
			if(size==1){//删除最后一个元素，要更新尾指针
				rear=head;
			}
		}else if(index==size-1){//删尾
			res=rear.data;
			Node p=head;
			while(p.next!=rear){
				p=p.next;
			}
			p.next=rear.next;
			rear=p;
		}else{//删中间
			Node p=head;
			for(int i=0;i<index;i++){
				p=p.next;
			}
			Node n=p.next;
			res=n.data;
			p.next=n.next;
			n=null;
		}
		size--;
		return res;
	}

	@Override
	public E removeFirst() {
		return remove(0);
	}

	@Override
	public E removeLast() {
		return remove(size-1);
	}

	@Override
	public void set(int index, E e) {
		if(index<0||index>=size){
			throw new IllegalArgumentException("角标非法");
		}
		Node p=head;
		for(int i=0;i<=index;i++){
			p=p.next;
		}
		p.data=e;
	}

	@Override
	public boolean contains(E e) {
		return find(e)!=-1;
	}

	@Override
	public int find(E e) {
		if(isEmpty()){
			return -1;
		}
		int index=-1;
		Node p=head;
		while(p.next!=null){
			index++;
			p=p.next;
			if(p.data.equals(e)){
				return index;
			}
		}
		return -1;
	}

	@Override
	public void removeElement(E e) {
		int index=find(e);
		if(index!=-1){
			remove(index);
		}
	}

	@Override
	public void clear() {
		head.next=null;
		rear=head;
		size=0;
	}
	@Override
	public String toString() {
		StringBuilder sb=new StringBuilder();
		if(isEmpty()){
			return "[]";
		}else{
			sb.append("[");
			Node p=head;
			while(true){
				p=p.next;
				if(p==rear){
					sb.append(p.data+"]");
					break;
				}else{
					sb.append(p.data+",");
				}
			}
		}
		return sb.toString();
	}
}

2.动态链表——栈的链式存储结构
可以通过单向链表实现链栈
LinkedStack单链栈类定义
1.定义类
public class LinkedStack implements Stack
2.定义成员变量
private LinkedList list //使用单链表来实现单链栈
3.定义构造函数
public LinkedStack() //创建空栈
4.定义成员函数
实现Stack接口函数
public String toString()//返回该栈的字符串形式

package 数据结构与算法;
import 数据结构与算法.Stack;
public class LinkedStack<E> implements Stack<E> {
	private LinkedList<E> list;
	public LinkedStack(){
		list=new LinkedList<>();
	}
	@Override
	public void push(E e) {
		list.addFirst(e);
	}
	@Override
	public E pop() {
		return list.removeFirst();
	}
	@Override
	public E peek() {
		return list.getFirst();
	}
	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}
	@Override
	public int getSize() {
		return list.getSize();
	}
	@Override
	public void clear() {
		list.clear();
	}
}

3.动态链表——队列的链式存储结构
可以通过单向链表实现单链队列
LinkedQueue单链栈类定义
1.定义类
public class LinkedQueue implements Queue
2.定义成员变量
private LinkedList list //使用单链表来实现队列
3.定义构造函数
public LinkedQueue() //创建空队列
4.定义成员函数
实现Queue接口函数
public String toString()//返回该队列的字符串形式
4.动态链表——单向循环链表
将单链表中尾结点的指针由空改为指向头结点（或第一个元素结点），就使整个单链表
形成一个环，这种头尾相接的单链表称为单循环链表，简称单向循环链表。
数据结构与算法_02【动态链表】
LinkedListSinglyCircular单向循环链表定义
1.定义类
public class LinkedListSinglyCircular implements List
2.定义成员变量
private Node head; //链表中头结点的头指针
private Node rear; //链表中尾结点的尾指针
private int size; //链表中元素的个数
private class Node{ //内部类，定义结点类 包含所存储的元素e和下一个
结点的地址next
E e;
Node next;
}
3.定义构造函数
public LinkedListSinglyCircular()
4.定义成员函数
实现List接口函数
public String toString()//返回该链表的字符串形式
5.动态链表——双向循环链表
双向循环链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域，再加上
收尾相接。
数据结构与算法_02【动态链表】
6.线性表总结
List接口
|——ArrayList 顺序表
|——LinkedList 单向链表
|——LinkedListSinglyCircular 单向循环链表
|——LinkedListDoubleCircular 双向循环链表
Stack接口
|——ArrayStack 顺序栈
|——ArrayStackDoubleEnd 双端顺序栈
|——LinkedStack 单向链栈
Queue接口
|——ArrayQueue 顺序队列
|——ArrayQueueLoop 顺序循环队列
|——LinkedQueue 单向链队列
顺序存储结构和链式存储结构的优缺点
存储分配方式
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能
查找：顺序O(1) 链式O(n)
增删：顺序O(n) 链式O(1)
空间性能
顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生溢出
链式存储结构不需预分配存储空间，只要有就可以分配，元素个数也不受限制
具体用什么存储方式，用什么数据结构，主要取决于实际的需求场景
1.游戏中背包，链式
2.手机通讯录，顺序
3.学生信息表，顺序
4.短信展示栏，链式
Java中对于线性表相关的常见内置类有哪些
java.util.Collection接口
|——List接口
|——ArrayList类
|——LinkedList类
|——Stack类
|——Queue接口
|——LinkedList类
|——ArrayDeque类（双端队列，基于数组实现）
|——PriorityQueue类（优先队列，基于二叉树实现，已不再线性表范畴内）
|——Deque接口
|——ArrayDeque类
|——LinkedList类

相关推荐