`

大话数据结构五:线性表的链式存储结构(双向链表)

 
阅读更多

1. 双向链表:在单链表的每个结点中,再设置一个指向其前驱结点的指针域,那么在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。


2. 单链表和双向链表比较:

单链表:总是要从头到尾找结点,只能正遍历,不能反遍历。

双向链表: 可以从头找到尾,也可以从尾找到头,即正反遍历都可以,可以有效提高算法的时间性能,但由于每个结点需要记录两份指针,所以在空间占用上略多一点,这就是通过空间来换时间。


3. Java实现双向链表:

// 双向链表
public class DoubleLinkedList<E> {
	private Node<E> head; // 头结点
	private int size; // 链表长度

	// 建立一个空链表
	public DoubleLinkedList() {
		head = null;
		size = 0;
	}
	
	// 在头结点前插入
	public boolean addBeforeHead(E data){
		Node<E> newNode = new Node<E>(data);
		if(isEmpty()){
			head = newNode;
		}else{
			head.setPrev(newNode);
			newNode.setNext(head);
			head = newNode;
		}
		size++;
		return true;
	}
	
	// 在链表尾部插入
	public boolean addAfterTail(E data){
		Node<E> newNode = new Node<E>(data);
		if(isEmpty()){
			head = newNode;
		}else{
			Node<E> tail = get(size);
			tail.setNext(newNode);
			newNode.setPrev(tail); // 设置新结点的上一结点
		}
		size++;
		return true;
	}

	// 插入指定位置的结点
	public boolean insert(int position, E data) {
		if(position >= 1 && (position <= size + 1)){
			Node<E> newNode = new Node<E>(data);
			if(isEmpty() || position == 1){ // 链表为空或在头结点前插入
				addBeforeHead(data);
			}else if(position == size + 1){ // 在尾结点后插入
				Node<E> preNode = get(position - 1);
				newNode.setPrev(preNode);
				preNode.setNext(newNode);
			}else{ // 在其他位置插入
				Node<E> preNode = get(position - 1); // 获取position的前一结点
				Node<E> afterNode = preNode.getNext(); // 获取未插入结点时position位置对应结点 
				newNode.setPrev(preNode); // ①
				newNode.setNext(afterNode); // ②
				afterNode.setPrev(newNode); // ③
				preNode.setNext(newNode); // ④
			}
			size++;
			return true;
		}
		return false;
	}

	// 删除指定位置的结点
	public E delete(int position) { 
		E result = null;
		if(position >= 1 && position <= size){
			if(position == 1){ // 删除头结点
				result = head.getData();
				Node<E> afterHead = head.getNext();
				afterHead.setPrev(null);
				head.setNext(null);
				head = afterHead; 
			}else if(position == size){ // 删除尾结点
				Node<E> preNode = get(position - 1); // 获取待删除结点的前一结点
				Node<E> delNode = preNode.getNext(); // 获取待删除结点
				result = delNode.getData();
				preNode.setNext(null);
			}else{ // 删除其他结点
				Node<E> preNode = get(position - 1); // 获取待删除结点的前一结点
				Node<E> delNode = preNode.getNext(); // 获取待删除结点
				result = delNode.getData();
				Node<E> nextNode = delNode.getNext();// 获取待删除结点的下一结点
				preNode.setNext(nextNode); // ①
				nextNode.setPrev(preNode); // ②
			}
			size--;
		}
		return result;
	}
	
	// 获取某个位置的结点(正序遍历)
	public Node<E> get(int position){
		Node<E> targetNode = null;
		if(!isEmpty() && position >= 1 && position <= size){ 
			targetNode = head;
			for(int i = 1; i < position ; i++){
				targetNode = targetNode.getNext(); // 循环获取对应位置的结点
			}
		}
		return targetNode;
	}
	
	// 获取链表的长度
	public int getSize(){
		return size;
	}
	
	// 判断链表是否为空
	public boolean isEmpty(){
		return size == 0;
	}
	
	// 打印链表数据
	public void display(){
		Node<E> node = head;
		System.out.print("双向链表: ");
		for(int i = 0; i < size; i++){
			System.out.print(" " + node.getData());
			node = node.getNext();
		}
		System.out.println("");
	}
}
//结点类,包含结点的数据和指向下一个节点的引用
public class Node<E> {
	private E data; // 数据域
	private Node<E> next; // 指针域保存着下一节点的引用
	private Node<E> prev; // 指针域保存着上一节点的引用 (相比单链表,双向链表多了这个指针)
	
	public Node() {
	}

	public Node(E data) {
		this.data = data;
	}

	public Node(E data, Node<E> next, Node<E> prev) {
		this.data = data;
		this.next = next;
		this.prev = prev;
	}

	public E getData() {
		return data;
	}

	public void setData(E data) {
		this.data = data;
	}

	public Node<E> getNext() {
		return next;
	}

	public void setNext(Node<E> next) {
		this.next = next;
	}

	public Node<E> getPrev() {
		return prev;
	}

	public void setPrev(Node<E> prev) {
		this.prev = prev;
	}
}
public class Main {
	public static void main(String[] args) {
		DoubleLinkedList<Integer> dll = new DoubleLinkedList<Integer>();
		dll.addBeforeHead(2);
		dll.addAfterTail(3);
		dll.addBeforeHead(1);
		dll.display();
		dll.insert(4,4);
		dll.insert(5,5);
		dll.insert(6,6);
		dll.display();
		dll.delete(6);
		dll.delete(3);
		dll.delete(1);
		dll.display();
		System.out.println("双向链表的长度为:  " + dll.getSize());
	}
}


分享到:
评论

相关推荐

    数据结构教学课件:线性表链表.ppt

    数据结构教学课件:线性表链表.ppt

    数据结构实验报告2线性表的链式存储结构.pdf

    数据结构实验报告2线性表的链式存储结构 本实验报告的主要内容是介绍线性表的链式存储结构,并通过编程实验来掌握线性表的逻辑结构和链式存储结构,以及单链表的基本算法。 一、线性表的概念 线性表是最基本的...

    利用C++实现以下经典数据结构算法:线性表、栈、队列、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法)、树.zip

    利用C++实现以下经典数据结构与算法:线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法...

    实验一:线性表的存储结构定义及基本操作.doc

    本实验的目的是让学生掌握线性表的顺序存储结构和链式存储结构的定义及基本操作,熟练掌握顺序表和链表的基本运算,理解循环链表和双链表的特点和基本运算,加深对顺序存储数据结构和链式存储数据结构的理解,并逐步...

    数据结构与算法:线性表的题库

    问题18:设a1、a2、a3为3个结点,整数P0、3、4代表地址,则如下的链式存储结构称为P034P0a13a24A30(A)循环链表 (B)单链表 (C)双向循环链表 (D)双向链表 答案:B 问题19:线性表是具有n个______...

    数据结构中线性表的链式存储

    ### 数据结构中线性表的链式存储及合并排序实现 #### 一、线性表的概念与链式存储介绍 线性表是数据结构中最基本的一种逻辑结构,它由n(n≥0)个数据元素组成的一个有限序列。线性表中的每个数据元素,除了第一个...

    数据结构:线性表、链表、队列、栈、串

    本主题将深入探讨线性表、链表、队列、栈这四种基本的数据结构,并以C++语言为例,通过相关源代码(stringData.cpp、seqList.cpp、node.cpp、seqQueue.cpp、linkQueue.cpp、linkStack.cpp、seqStack.cpp)来解析其...

    哈工大数据结构实验一_一元多项式计算器

    实验项目:线性表的链式存储结构与应用 实验题目:一元多项式计算器 实验内容: 设计线性表的动态或者静态链式存储结构,并实现一个一元多项式的计算器。 实验要求: 以动态或者静态链表存储一元多项式,在此基础上...

    关于线性表的顺序存储和链式存储结构的实验报告

    线性表是数据结构中的一个基本概念,它是一种在计算机内存中能够按照线性方式存储数据元素的结构。线性表的元素之间存在一对一的线性关系。在数据结构实验报告中,线性表的存储结构被分为两大类:顺序存储结构和链式...

    数据结构:线性表顺序存储

    线性表是计算机科学中一种基础且重要的数据结构,它由有限个相同类型的数据元素构成一个有序序列。在描述线性表时,我们通常强调以下四个特性:存在唯一的第一个元素和最后一个元素,以及除了两端元素外,每个元素都...

    数据结构实验报告2线性表的链式存储结构.doc

    在实际应用中,链式存储结构常用于实现各种复杂数据结构,如图和树。在处理不确定数据量或频繁进行插入、删除操作的场景下,链式存储通常比顺序存储更优。实验报告的编写有助于巩固理论知识,提高实践能力,同时培养...

    数据结构_线性表的链式存储

    线性表是计算机科学中一种基础的数据结构,它是由相同类型元素构成的有限序列。在本实验中,我们将深入理解并实践线性表的链式存储结构,这是一种非顺序存储方式,与数组不同,它通过指针链接元素,使得元素在内存中...

    数据结构:线性表(链接存储).ppt

    数据结构:线性表(链接存储) 一、线性表的链接存储 线性表的链接存储是一种存储方式,它可以克服顺序存储的缺点。顺序存储需要一块连续的存储空间,但是当顺序表很大时,系统可能无法分配这么大的一块连续存储...

    《数据结构C++版》实验一:线性表的顺序存储结构实验报告

    《数据结构C++版》实验一的目的是让学生深入理解线性表的顺序存储结构,并熟练掌握C++程序设计的基本技巧。在这个实验中,学生需要通过类的定义来实现线性表,数据对象的类型可以自定义。以下是实验涉及的主要知识点...

    数据结构: 线性表讲解实例

    数据结构: 线性表讲解实例。针对线性表的深入讲解。

    数据结构实验一线性表的基本操作.docx

    数据结构实验一线性表的基本操作 一、线性表的概念和类型 线性表是一种基本的数据结构,它是一种由零个或多个元素组成的有限序列,每个元素都是数据类型的实例。线性表可以分为两种类型:顺序存储结构和链式存储...

    数据结构作业:第2章-线性表作业题目.docx

    "数据结构作业:第2章-线性表作业题目.docx" 在这份作业中,我们可以总结出以下几个重要的知识点: 1. 线性表的存储方式:线性表可以采用顺序存储和链式存储两种方式。顺序存储方式是指将所有元素存储在一片连续的...

    c语言数据结构实验:掌握线性表的链式存储结构 熟练掌握循环链表的存储特征和建立方法,掌握线性表的链式存储结构 下面是源码的txt

    2、已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母、数字和其它字符),设计算法构造三个以循环链表示的线性表,使每一个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的空间。...

    数据结构 线性表 链表

    线性表是一种基础且重要的数据结构,它由n个数据元素组成的一个有限序列。这些元素通常是同一类型,具有均匀性,比如数学中的数列、英文字母表或者一个单位的电话号码簿。线性表的特点包括相邻性、有限性和有序性。...

Global site tag (gtag.js) - Google Analytics