/**
* 双向循环链表测试
* @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`是一种常用的线性数据结构,它通过节点(Node)对象存储数据,并且每个节点都包含指向前后节点的引用,从而形成一个双向循环链表。这个链表的特点在于,它的首节点和尾节点相互连接,...
非循环链表的尾部没有链接回头部,因此遍历链表时,当到达尾部的后继为空时,即可停止,避免了无限循环的风险。这对于编写遍历或搜索算法来说,简化了逻辑处理。 四、Java实现 在Java中,双向链表可以使用内置的`...
本项目涵盖了单向链表、双向链表和循环链表三种类型,它们各自有不同的特点和用途。 1. **单向链表**: 单向链表只允许从一个方向遍历,每个节点包含两部分:数据元素和指向下一个节点的引用。在Java中,可以定义...
在本项目中,我们将探讨三种不同的链表类型:单链表、单向循环链表和双向循环链表。下面将详细阐述这些链表的实现和它们的特性。 首先,单链表是一种线性数据结构,每个节点包含两个部分:数据元素和指向下一个节点...
在C++中实现双向循环链表涉及到了数据结构和算法的知识。双向循环链表是一种特殊类型的链表,其中每个节点不仅包含数据,还包含两个指针,分别指向其前一个和后一个节点。这种结构允许从链表的任何位置进行前向和后...
本文实例讲述了C#双向链表LinkedList排序实现方法。分享给大家供大家参考。具体如下: 1.函数 打印链表函数PrintLinkedList 和 排序函数SortLinkedList 注:下面代码中的链表每项都是double类型,如果换做其他的类型...
- 链表:如单向链表、双向链表和循环链表等。 - 栈:一种后进先出(LIFO)的数据结构,用于表达式求值、函数调用栈等。 #### 二、非线性结构 非线性结构指的是数据元素间的关系不是简单的线性关系,而是更复杂的...
3. 循环链表(CircularLinkedList):单向循环链表和双向循环链表是在单链表和双向链表的基础上,将最后一个节点的Next指针或双向链表的Prev和Next指针指向头节点,形成一个环形结构。循环链表没有明确的链头和链尾...
链表有多种类型,包括单向链表、双向链表和循环链表。 1. **单向链表**:每个节点仅有一个指针指向下一个节点,没有指向前一个节点的链接。插入和删除操作只需要改变相邻节点的指针,不需要像数组那样移动元素。 2...
dnode.h: 双向循环链表结点 treenode.h: 二叉树结点 avltreenode.h: AVL 树结点 array.h: 安全数组,可自动增长大小(随机访问,但扩充时效率低) linkedlist.h: 普通链表(可随机访问,但访问效率低) ...
LinkedList是双向循环链表,适合频繁添加和删除元素;Vector与ArrayList类似,但它是线程安全的。 - **Map**:键值对的集合,Key唯一,Value可以重复。常见的实现有HashMap、TreeMap、Hashtable、...
循环链表 静态链表 栈(Stack) 队列(Queue) 双端队列(Deque) 循环队列 哈希表(HashTable) 树形数据结构 二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) 平衡二叉搜索树...
1. **链表的类型**:链表主要有单链表、双向链表和循环链表三种形式。单链表每个节点仅有一个指向前一个节点的指针;双向链表则包含两个指针,分别指向前后两个节点;循环链表最后一个节点的指针会指向链表的第一个...
根据指针的方向,链表可以分为单向链表、双向链表和循环链表。 1. **单向链表**:每个节点只有一个指针,指向下一个节点。只能从头到尾进行遍历,不能反向遍历。插入和删除操作通常比数组快,因为只需要改变相邻...
在Java中,有多种类型的链表,包括单链表、双链表和循环链表等。本程序可能是针对这些链表类型的一种实现,用于Java考试复习。在Java中,`java.util.LinkedList`类是内置的链表实现,它继承了`...
标题“LinkedList.zip”暗示了这个压缩包可能包含了多种链表类型的实现,包括单向链表、单向环形链表、双向链表和双向环形链表。这些链表各有特点,用途广泛: 1. **单向链表(Singly Linked List)**:每个节点包含...
此外,还可以进一步扩展功能,比如支持双向链表、循环链表,或者实现更复杂的链表操作,如查找、排序等。 总的来说,MFC提供的类库和事件驱动模型为实现链表程序提供了便利。通过理解MFC的机制和链表的基本操作,...
链表是一种重要的数据结构,它在计算机科学中用于存储和管理动态集合。...`listTab_VB的链表`可能是包含示例代码和说明的文件,通过学习这个文件,你可以更深入地理解如何在VB中实现和使用链表及其相关数据结构。
而Java的LinkedList类则基于无头双向循环链表实现。链表的主要优势在于插入和删除操作的高效性,尤其是在链表头部或尾部,时间复杂度仅为O(1)。 对于链表的操作,常见的面试题目包括删除所有等于特定值的节点、反转...