`

数据结构学习笔记-链表中的双向链表(JAVA)

    博客分类:
  • Java
 
阅读更多

概念:
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,
分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,
都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
实现方式:构造一个常驻内存的头节点引用,然后头节点的上一个节点是最后一个节点,最后
一个节点的下一个是头节点。其他的每个节点都有上下节点的引用。最少有一个头节点
操作:构造链表,销毁链表,计算元素个数,返回链表中指定链表中元素的值,插入元素,删除元素
代码:
package com.alg.link;
import java.util.Iterator;
//双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,
//分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,
//都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
//链表的操作有:构造链表,销毁链表,计算元素个数,返回链表中指定链表中元素的值,插入元素,删除元素

public class DoubleWayLinkedList<T> extends BaseLinkedList<T>
{
    transient Link<T> voidLink;
    public DoubleWayLinkedList()
    {
        voidLink = new Link<T>(null, null, null);
        voidLink.previous = voidLink;
        voidLink.next = voidLink;
    }
    // 向尾部添加
    @Override
    public void add(T object)
    {
        Link<T> oldLast = voidLink.previous;
        // 末尾的上一个是最后一下,下一个是第一个
        Link<T> newLink = new Link<T>(object, oldLast, voidLink);
        voidLink.previous = newLink;
        oldLast.next = newLink;
        modCount++;
        size++;
    }
    @Override
    public void clear()
    {
        if (size > 0)
        {
            size = 0;
            voidLink.next = voidLink;
            voidLink.previous = voidLink;
            modCount++;
        }
    }
    @Override
    public T get(int location)
    {
        if (0 <= location && location < size)
        {
            Link<T> link = voidLink;
            if (location < (size / 2))
            {
                for (int i = 0; i <= location; i++)
                {
                    link = link.next;
                }
            }
            else
            {
                for (int i = size; i > location; i--)
                {
                    link = link.previous;
                }
            }
            return link.data;
        }
        return null;
    }
    // 移除某个元素
    @Override
    public T remove(int location)
    {
        if (0 <= location && location < size)
        {
            Link<T> link = voidLink;
            if (location < (size / 2))
            {
                for (int i = 0; i <= location; i++)
                {
                    link = link.next;
                }
            }
            else
            {
                for (int i = size; i > location; i--)
                {
                    link = link.previous;
                }
            }
            Link<T> previous = link.previous;
            Link<T> next = link.next;
            previous.next = next;
            next.previous = previous;
            size--;
            modCount++;
            return link.data;
        }
        return null;
    }
    // 可以加入空的数据,所以有object为null的移除,而且移的是第一个数据为null的
    @Override
    public boolean remove(Object object)
    {
        Link<T> link = voidLink.next;
        if (object != null)
        {
            while (link != voidLink && !object.equals(link.data))
            {
                link = link.next;
            }
        }
        else
        {// 如果data为null,则碰到了第一个空数据
            while (link != voidLink && link.data != null)
            {
                link = link.next;
            }
        }
        if (link == voidLink)
        {
            return false;
        }
        Link<T> next = link.next;
        Link<T> previous = link.previous;
        previous.next = next;
        next.previous = previous;
        size--;
        modCount++;
        return true;
    }
    @Override
    public int size()
    {
        return size;
    }
    public Iterator<T> iterator()
    {
        return new SimpleIterator();
    }
}
  • Alg.rar (19.9 KB)
  • 下载次数: 2
分享到:
评论

相关推荐

    leetcode-链表笔记

    链表是一种基础且重要的数据结构,它在计算机科学和编程中扮演着至关重要的角色,特别是在算法和数据结构的学习中,LeetCode 是一个很好的实践平台。本笔记将深入探讨 LeetCode 中涉及的链表相关问题,旨在帮助你...

    java链表 个人总结

    在Java中,LinkedList的节点类是Node,它包含了三个字段:data(存储数据)、next(指向下一个节点)和prev(在双向链表中指向前一个节点)。当我们使用LinkedList时,可以通过addFirst()、addLast()、add()、remove...

    JAVA数据结构笔记

    本笔记主要涵盖了从第一章到第六章关于数据结构和Java语言的相关知识点。 第一章介绍了数据结构的基本概念,包括面向对象的特性如对象、继承和多态,对比了C++和Java中的指针差异。在Java中,垃圾回收机制自动管理...

    《Java数据结构和算法》学习笔记(4)——链表

    进一步学习,可以研究双向链表,它允许在节点的前后进行插入和删除,提高了操作的灵活性。循环链表则形成一个闭合的环,可以简化某些循环操作。 总之,链表是数据结构的基础,理解和熟练运用链表对于提升编程技能...

    个人笔记--Java_API

    - `LinkedList`:底层为双向链表,适合频繁插入和删除操作。 - `Vector`:线程安全的`ArrayList`版本。 - `Stack`:继承自`Vector`,模拟栈结构。 **1.6 Set接口** - **特点**:无序且不允许重复元素。 - **...

    链表树-复合数据结构应用实例.zip

    本压缩包“链表树-复合数据结构应用实例.zip”显然是针对大学生C/C++/JAVA/Python数据结构学习的资源集合,涵盖了这些编程语言的数据结构实现和实践。 首先,让我们深入了解链表。链表是一种线性数据结构,与数组...

    《恋上数据结构》第1季度 + 第2季 完整学习笔记,从0实现的 Java 数据结构大全。.zip

    《恋上数据结构》的学习笔记涵盖了第一季和第二季的内容,旨在帮助初学者从零开始全面掌握Java实现的数据结构。在这个压缩包中,尽管具体的文件名“dfadfasdkj”并未提供足够的信息,我们可以推测它可能包含了一系列...

    良葛格Java 学习笔记(繁体全)

    - **数组**:Java中的数组是一种存储固定数量同类型元素的数据结构,理解其创建、访问和操作方法至关重要。 2. **面向对象编程**: - **类与对象**:Java是一种面向对象的语言,类是对象的模板,对象是类的实例。...

    学习笔记 java\CoreJava笔记\CoreJava_day15

    以下是对"CoreJava_day15"学习笔记中可能涉及的一些关键知识点的详细解释: 1. **异常处理**: - 异常是程序运行时出现的错误,Java通过Exception类及其子类来表示这些错误。在Java中,异常处理使用try-catch-...

    Java基础(韩顺平版)笔记详

    - 数组是用来存储相同类型元素的一种数据结构。 - 数组的长度固定,在创建时确定。 - 数组元素可以通过索引访问,索引从0开始。 - **字符串** - String类用于表示不可变的字符序列。 - StringBuilder和...

    java技术从入门到精通(孙鑫)学习笔记Lesson 6(数据结构).doc

    在Java编程语言中,数据结构是程序设计的基础,它决定了如何有效地存储和处理数据。本篇笔记主要讨论了几个关键的数据结构,包括LinkedList、ArrayList以及HashSet,并通过实例展示了它们的用法。 首先,LinkedList...

    Java入门学习笔记

    ### Java入门学习笔记 #### 一、Java特点与运行原理 **1.1 Java特点** - **简单性:** Java的设计使得它易于学习且避免了许多传统编程语言中存在的复杂性。 - **面向对象:** Java是一种纯面向对象的语言,支持...

    常见数据结构及算法(Java语言描述).zip

    数据结构与算法是计算机科学的基础,对于任何...这个压缩包中的学习笔记和资料可以帮助大学生深入理解这些概念,并通过Java实践提升编程能力。无论你是初学者还是有经验的开发者,这些资源都将是你提升技能的宝贵财富。

    java私塾学习笔记整理

    ### Java私塾学习笔记整理 #### 第一章:Java入门 **一、Java是什么?** Java是一种广泛使用的高级编程语言,由Sun Microsystems于1995年推出。它旨在为跨平台开发提供一种通用的语言环境,使开发者能够在任何...

    集合-黑马程序员Java学习笔记

    本学习笔记由黑马程序员提供,旨在帮助初学者深入理解Java中的集合框架及其使用方法。 首先,我们来探讨“集合”的基本概念。在Java中,集合是一个对象容器,可以容纳多个元素,这些元素可以是任意类型的数据。Java...

    关于入门单链表的基本操作

    理解并熟练掌握这些基本操作对于理解和应用更复杂的数据结构,如双向链表、循环链表、链表栈和链表队列至关重要。同时,它们也是解决算法问题的基础,比如在面试中常见的链表相关问题。因此,对于任何想要进入IT行业...

    学习笔记 java\CoreJava笔记\CoreJava_day11

    CoreJava_day11的学习笔记主要涵盖了集合框架,特别是关于List、Set和Map接口,以及ArrayList、Vector和LinkedList等具体实现类的知识点。 首先,集合框架是用来存放对象的对象,它提供了一组接口和类,使得我们...

    JAVA 数据处理笔记

    数组是Java中最基本的数据结构,用于存储相同类型的元素序列。创建数组时需要指定元素类型和大小,一旦创建,大小不可变。数组提供了下标访问元素(通过索引)的方式,索引从0开始。数组操作包括初始化、赋值、遍历...

Global site tag (gtag.js) - Google Analytics