`
coach
  • 浏览: 386725 次
  • 性别: Icon_minigender_2
  • 来自: 印度
社区版块
存档分类
最新评论

LinkedList学习(双向循环链表)

 
阅读更多
/**
 * 双向循环链表测试
 * @author coach
 * @param <E>
 */
public class Node<E> 
{
    private E element;            //结点数据
    private Node<E> next;        //上结点
    private Node<E> previous;    //下结点
    private static int size=0;    //链表长

    //默认关结点next previous都是空,
    public Node()
    {
        this.element=null;
        this.next=null;
        this.previous=null;
    }
    
    private Node(E element,Node<E> next,Node<E> previous)
    {
        this.element=element;
        this.next=next;
        this.previous=previous;
    }

    /**
     * 尾部添加元素 e
     * @param e
     */
    public void addAfter(E e)
    {
        //定义新结点,next-->头结点;previous-->头结点.previous(尾结点)
        Node<E> newNode=new Node<E>(e,this,this.previous==null?this:this.previous);
        //头结点next为空则让它指向newNode
        if(this.next==null)
        {
            this.next=newNode;
        }
        //头结点previous为空则让它指向newNode
        if(this.previous==null)
        {
            this.previous=newNode;
        }
        this.previous.next=newNode;
        this.previous=newNode;
        size++;
    }
    /**
     * 头部添加元素 e
     * @param e
     */
    public void addBefor(E e)
    {
        Node<E> newNode=new Node<E>(e,this.next==null?this:this.next,this);
        if(this.next==null)
        {
            this.next=newNode;
        }
        if(this.previous==null)
        {
            this.previous=newNode;
        }
        this.next.previous=newNode;
        this.next=newNode;
        size++;
    }
    /**
     * 在index处添加元素e
     * @param e
     * @param index
     */
    public void add(E e,int index)
    {
        //索引越界
        if(index>=size || index<0)
        {
            throw new IndexOutOfBoundsException("Node.get():"+index);
        }
        else
        {
            //index>size/2,反向遍历
            if(index>size>>1)
            {
                Node<E> temp=this;
                for(int i=size;i>index;i--)
                {
                    temp=temp.previous;
                }
                Node<E> newNode=new Node<E>(e,temp,temp.previous);
                temp.previous.next=newNode;
                temp.previous=newNode;
            }
            else
            {
                Node<E> temp=this;
                for(int i=0;i<=index;i++)
                {
                    temp=temp.next;
                }
                Node<E> newNode=new Node<E>(e,temp,temp.previous);
                temp.previous.next=newNode;
                temp.previous=newNode;
            }
            size++;
        }
    }
    /**
     * 删除第index个元素
     * @param index
     */
    public void remove(int index)
    {
        //索引越界
        if(index>=size || index<0)
        {
            throw new IndexOutOfBoundsException("Node.get():"+index);
        }
        else
        {
            //index>size/2,反向遍历
            if(index>size>>1)
            {
                Node<E> temp=this;
                for(int i=size;i>index;i--)
                {
                    temp=temp.previous;
                }
                temp.previous.next=temp.next;
                temp.next.previous=temp.previous;
            }
            else
            {
                Node<E> temp=this;
                for(int i=0;i<=index;i++)
                {
                    temp=temp.next;
                }
                temp.previous.next=temp.next;
                temp.next.previous=temp.previous;
            }
            size--;
        }
    }

    /**
     * 取得第index个元素
     * @param index
     * @return
     */
    public E get(int index)
    {
        //索引越界
        if(index>=size || index<0)
        {
            throw new IndexOutOfBoundsException("Node.get():"+index);
        }
        else
        {
            //index>size/2,反向遍历
            if(index>size>>1)
            {
                Node<E> temp=this;
                for(int i=size;i>index;i--)
                {
                    temp=temp.previous;
                }
                return temp.element;
            }
            else
            {
                Node<E> temp=this;
                for(int i=0;i<=index;i++)
                {
                    temp=temp.next;
                }
                return temp.element;
            }
        }
    }
    public int size()
    {
        return size;
    }
    
    public static void main(String a[])
    {
        Node node=new Node();
        node.addAfter("1");
        node.addAfter("2");
        node.addAfter("3");
        node.addBefor("0");
        node.add("7", 0);
        System.out.println(node.get(0) );
        System.out.println(node.get(1) );
        System.out.println(node.get(2) );
        System.out.println(node.get(3) );
        System.out.println(node.get(4) );
        
    }
}
分享到:
评论

相关推荐

    简单的双向循环链表

    本文将深入探讨“简单的双向循环链表”,并结合提供的`LinkedList.java`源码来理解其实现原理。 双向循环链表与单向链表不同,它在每个节点中不仅保存了指向下一个节点的指针,还保存了指向前一个节点的指针,这种...

    用Java实现模拟双向循环链表LinkedList

    在Java编程语言中,`LinkedList`是一种常用的线性数据结构,它通过节点(Node)对象存储数据,并且每个节点都包含指向前后节点的引用,从而形成一个双向循环链表。这个链表的特点在于,它的首节点和尾节点相互连接,...

    Java有序非循环双向链表算法实例

    非循环链表的尾部没有链接回头部,因此遍历链表时,当到达尾部的后继为空时,即可停止,避免了无限循环的风险。这对于编写遍历或搜索算法来说,简化了逻辑处理。 四、Java实现 在Java中,双向链表可以使用内置的`...

    LinkedList:该项目提供了单向、双向和循环链表的示例

    本项目涵盖了单向链表、双向链表和循环链表三种类型,它们各自有不同的特点和用途。 1. **单向链表**: 单向链表只允许从一个方向遍历,每个节点包含两部分:数据元素和指向下一个节点的引用。在Java中,可以定义...

    list-2_单链表_speakgfp_数据结构_循环链表_

    在本项目中,我们将探讨三种不同的链表类型:单链表、单向循环链表和双向循环链表。下面将详细阐述这些链表的实现和它们的特性。 首先,单链表是一种线性数据结构,每个节点包含两个部分:数据元素和指向下一个节点...

    如何用C++实现双向循环链表

    在C++中实现双向循环链表涉及到了数据结构和算法的知识。双向循环链表是一种特殊类型的链表,其中每个节点不仅包含数据,还包含两个指针,分别指向其前一个和后一个节点。这种结构允许从链表的任何位置进行前向和后...

    C#双向链表LinkedList排序实现方法

    本文实例讲述了C#双向链表LinkedList排序实现方法。分享给大家供大家参考。具体如下: 1.函数 打印链表函数PrintLinkedList 和 排序函数SortLinkedList 注:下面代码中的链表每项都是double类型,如果换做其他的类型...

    线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf

    - 链表:如单向链表、双向链表和循环链表等。 - 栈:一种后进先出(LIFO)的数据结构,用于表达式求值、函数调用栈等。 #### 二、非线性结构 非线性结构指的是数据元素间的关系不是简单的线性关系,而是更复杂的...

    链表的数据结构学习.pdf

    3. 循环链表(CircularLinkedList):单向循环链表和双向循环链表是在单链表和双向链表的基础上,将最后一个节点的Next指针或双向链表的Prev和Next指针指向头节点,形成一个环形结构。循环链表没有明确的链头和链尾...

    linkedList_DSA:链表与C ++

    链表有多种类型,包括单向链表、双向链表和循环链表。 1. **单向链表**:每个节点仅有一个指针指向下一个节点,没有指向前一个节点的链接。插入和删除操作只需要改变相邻节点的指针,不需要像数组那样移动元素。 2...

    VC++常用的数据结构类源码

    dnode.h: 双向循环链表结点 treenode.h: 二叉树结点 avltreenode.h: AVL 树结点 array.h: 安全数组,可自动增长大小(随机访问,但扩充时效率低) linkedlist.h: 普通链表(可随机访问,但访问效率低) ...

    Java 72道面试题和答案.docx

    LinkedList是双向循环链表,适合频繁添加和删除元素;Vector与ArrayList类似,但它是线程安全的。 - **Map**:键值对的集合,Key唯一,Value可以重复。常见的实现有HashMap、TreeMap、Hashtable、...

    Java超详细!Java实现数据结构PPT课件

    循环链表 静态链表 栈(Stack) 队列(Queue) 双端队列(Deque) 循环队列 哈希表(HashTable) 树形数据结构 二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) 平衡二叉搜索树...

    C语言课件包括链表等

    1. **链表的类型**:链表主要有单链表、双向链表和循环链表三种形式。单链表每个节点仅有一个指向前一个节点的指针;双向链表则包含两个指针,分别指向前后两个节点;循环链表最后一个节点的指针会指向链表的第一个...

    链表的基本操作,插入删除查找等

    根据指针的方向,链表可以分为单向链表、双向链表和循环链表。 1. **单向链表**:每个节点只有一个指针,指向下一个节点。只能从头到尾进行遍历,不能反向遍历。插入和删除操作通常比数组快,因为只需要改变相邻...

    java链表的程序

    在Java中,有多种类型的链表,包括单链表、双链表和循环链表等。本程序可能是针对这些链表类型的一种实现,用于Java考试复习。在Java中,`java.util.LinkedList`类是内置的链表实现,它继承了`...

    LinkedList.zip

    标题“LinkedList.zip”暗示了这个压缩包可能包含了多种链表类型的实现,包括单向链表、单向环形链表、双向链表和双向环形链表。这些链表各有特点,用途广泛: 1. **单向链表(Singly Linked List)**:每个节点包含...

    用MFC做的链表程序

    此外,还可以进一步扩展功能,比如支持双向链表、循环链表,或者实现更复杂的链表操作,如查找、排序等。 总的来说,MFC提供的类库和事件驱动模型为实现链表程序提供了便利。通过理解MFC的机制和链表的基本操作,...

    VB中实现链表

    链表是一种重要的数据结构,它在计算机科学中用于存储和管理动态集合。...`listTab_VB的链表`可能是包含示例代码和说明的文件,通过学习这个文件,你可以更深入地理解如何在VB中实现和使用链表及其相关数据结构。

    8.顺序表和链表新1

    而Java的LinkedList类则基于无头双向循环链表实现。链表的主要优势在于插入和删除操作的高效性,尤其是在链表头部或尾部,时间复杂度仅为O(1)。 对于链表的操作,常见的面试题目包括删除所有等于特定值的节点、反转...

Global site tag (gtag.js) - Google Analytics