`
uule
  • 浏览: 6351744 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

双向链表

 
阅读更多

 

JAVA实现双向链表终极解析!!熟练使用接口

 

 

注意:

get、set、add、remove、entry、clear

 

注意entry的循环:

       for (Entry e = header.previous; e != header; e = e.previous) {}  

 

新节点的创建: 

Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  

 

此时新加节点已知道其前后节点,但其前节点并不知道后节点发生变化,后节点也不知道前节点发生变化,所以分别将新节点赋给他们。

 

 

双向链表节点:

private static class Entry<E> {    
        E element;    
        Entry<E> next;    
        Entry<E> previous;    
        
        Entry(E element, Entry<E> next, Entry<E> previous) {    
            this.element = element;    
            this.next = next;    
            this.previous = previous;    
        }    
    } 

 

实现:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
        
	private transient Entry<E> header = new Entry<E>(null, null, null);    
      
	public LinkedList() {    
		header.next = header.previous = header;    
	} 
    
	public E get(int index) {
		return entry(index).element;
	}
	
	public E set(int index, E element) {
		Entry<E> e = entry(index);
		E oldVal = e.element;
		e.element = element;
		return oldVal;
	}
	
	//  根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历    
	private Entry<E> entry(int index) {      
		if (index < 0 || index >= size)      
		    throw new IndexOutOfBoundsException("Index: "+index+      
							", Size: "+size);      
		Entry<E> e = header;      
		if (index < (size >> 1)) { //如果较靠近有表头      
		    for (int i = 0; i <= index; i++)      
			e = e.next;      
		} else { //较靠近表尾      
		    for (int i = size; i > index; i--)      
			e = e.previous;      
		}      
		return e;      
	}   
	
	
	//默认的添加动作,可以看到这个方法是把新元素添加 到表尾    
	public boolean add(E e) {      
		addBefore(e, header); //加到头结点之前 ,即表尾      
		return true;      
	}
	
	private Entry<E> addBefore(E e, Entry<E> entry) {      
		 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);      
		 newEntry.previous.next = newEntry; //将新结点与前后结点相连接       
		 newEntry.next.previous = newEntry;      
		 size++;      
		 modCount++;      
		 return newEntry;      
	}
	
	 //默认的删除动作是删除链表的第一个元素,所以说在默认情况下,LinkedList其实扮*演的是一个队列的角色    
	public E remove() {      
		 return removeFirst();      
	}
	
	public E removeFirst() {
		return remove(header.next);
	}
	
	private E remove(Entry<E> e) {
		if (e == header)
			throw new NoSuchElementException();

		E result = e.element;
		e.previous.next = e.next;
		e.next.previous = e.previous;
		e.next = e.previous = null;
		e.element = null;
		size--;
		modCount++;
		return result;
	}
	
	
	public void clear() {
		Entry<E> e = header.next;
		while (e != header) {
			Entry<E> next = e.next;
			e.next = e.previous = null;
			e.element = null;
			e = next;
		}
		header.next = header.previous = header;
		size = 0;
		modCount++;
	}
}

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    支持类模版的C++双向链表

    在C++编程中,双向链表是一种非常重要的数据结构,它允许在列表的任一位置进行插入和删除操作,而不必像数组那样依赖于索引。在这个“支持类模版的C++双向链表”中,我们将探讨如何利用C++的模板特性来实现一个灵活...

    Linux内核双向链表简单分析

    ### Linux内核双向链表简单分析 #### 链表数据结构简介 链表作为一种基本且重要的数据结构,在操作系统及各种软件系统中扮演着至关重要的角色。尤其在Linux内核中,链表更是广泛应用于内存管理、进程调度、文件...

    双向链表双向链表双向链表

    双向链表是一种高级数据结构,它在计算机科学中被广泛应用于各种算法和程序设计中。与单链表相比,双向链表的主要特点是每个节点不仅包含指向下一个节点的指针,还包含一个指向前一个节点的指针。这种设计使得双向...

    C++双向链表统计文章单词出现频率

    在这个特定的项目中,“C++双向链表统计文章单词出现频率”是一个涉及数据结构和算法的应用,目标是实现一个程序来分析文本文件,计算并显示文章中每个单词出现的次数。双向链表作为数据结构的核心,其特点是每个...

    双向链表的操作

    双向链表的操作问题 Time Limit: 1000MS Memory Limit: 10000KB Submissions: 111 Accepted: 41 Description 建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成...

    java 单链表和双向链表的实现

    本话题主要探讨两种常用的数据结构——单链表和双向链表在Java中的实现,以及相关的操作,如在头部添加节点、在尾部添加节点、遍历、逆置和删除。 首先,我们来理解单链表和双向链表的基本概念。单链表是一种线性...

    创建双向链表_双向链表_

    双向链表是一种特殊类型的数据结构,与常见的单向链表相比,它具有更丰富的操作能力,可以支持前后两个方向的遍历。本篇文章将深入探讨如何创建双向链表以及其在增加和删除操作中的应用。 双向链表的每个节点不仅...

    操作系统课设-线程安全的双向链表

    操作系统课程设计中实现线程安全的双向链表是一项重要的实践任务,这涉及到多线程编程、数据结构以及并发控制等核心知识点。在这个项目中,我们主要关注如何在多线程环境下构建一个能够正确操作(如插入、删除)而不...

    双向链表的增删改查

    双向链表(Double Linked List)是链表的一种变体,它允许我们在列表中的每个节点处进行前向和后向的遍历。本文将详细探讨如何实现双向链表的增、删、改、查操作,并通过C++编程语言的DLink.cpp文件进行实际应用。 ...

    数据结构-双向链表

    双向链表是一种特殊的数据结构,它在编程中具有重要的应用。本文将深入探讨双向链表的概念,实现,以及如何进行基本操作。 双向链表,顾名思义,是一种链式存储结构,其中每个节点包含两个指针,一个指向前一个节点...

    stm32f103 双向链表

    在这个项目中,我们讨论的是如何在STM32F103上实现一个双向链表的数据结构。双向链表是一种特殊的数据结构,它允许我们在列表中的节点之间进行前向和后向的移动,这在处理动态数据集合时非常有用。 首先,我们要...

    用双向链表做的n的阶乘

    在编程领域,双向链表是一种数据结构,它允许在列表中的元素之间进行前向和后向的导航。这种数据结构在处理需要频繁插入、删除或遍历操作的问题时特别有用。而“n的阶乘”是数学概念,表示1到n的所有整数的乘积,记...

    数据结构源代码之双向链表

    ### 数据结构源代码之双向链表 #### 概述 本文档主要介绍如何通过C语言实现双向链表的基本操作。继单链表之后,双向链表作为一种更灵活的数据结构,支持从前向后以及从后向前的遍历。双向链表在每个节点中除了包含...

    数据结构 双向链表(C++)

    双向链表是一种特殊的数据结构,它在计算机程序设计中扮演着重要角色,特别是在C++这样的编程语言中。本节将深入探讨双向链表的概念、其结构、操作以及C++中的实现。 双向链表与单链表不同,它允许每个节点不仅有一...

    大数阶乘 双向链表

    本主题聚焦于如何使用双向链表这一数据结构来实现大数阶乘的计算。双向链表允许我们有效地存储和操作大数,同时保持良好的性能。 首先,我们需要了解双向链表的基本概念。双向链表是一种线性数据结构,其中每个节点...

    双向链表实现结点类

    定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及左结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...

    C++经典算法 双向链表

    ### C++经典算法:双向链表 在计算机科学领域中,数据结构是极其重要的基础知识之一。其中链表作为一种常见的线性表实现方式,在各种应用场景中都有广泛的应用。本篇文章将根据给定的代码片段深入探讨双向链表的...

    双向链表模板类简单实现

    本文将深入探讨双向链表及其在C++中的模板类实现,以"双向链表模板类简单实现"为主题,我们来详细了解一下这个话题。 双向链表,与单向链表不同,它的每个节点不仅包含数据,还包含两个指针,一个指向下一个节点...

    C语言编写的双向链表

    双向链表是链表的一种变体,它在每个节点中不仅存储了数据,还包含了指向前后节点的指针,这使得在链表中的导航变得更加灵活。 双向链表的结构: 在C语言中,一个双向链表的节点通常包含三个部分:数据域,以及两个...

    双向链表.cpp 双向链表类定义及测试代码 c++

    双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材

Global site tag (gtag.js) - Google Analytics