代码来自教科书。
public class MyLinkedList<T> implements Iterable<T>
{
private int theSize;
private Node<T> begin;//头指针,哑的,第一个数据的前面
private Node<T> end;//尾指针,哑的,最后一个数据的后面
public MyLinkedList( )
{
clear( );
}
public void clear( )
{
begin = new Node<T>( null, null, null );
end = new Node<T>( null, begin, null );
begin.next = end;
theSize = 0;
}
public int size( )
{
return theSize;
}
public boolean isEmpty( )
{
return size( ) == 0;
}
//在尾端添加一个
public boolean add( T x )
{
add( size( ), x );
return true;
}
//在索引idx处添加
public void add( int idx, T x )
{
addBefore( getNode( idx, 0, size( ) ), x );
}
//在节点P之前加一个节点
private void addBefore( Node<T> p, T x )
{
Node<T> newNode = new Node<T>( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
}
//获取索此处节点数据
public T get( int idx )
{
return getNode( idx ).data;
}
//将索引idx处节点的值更换为nuwVal
public T set( int idx, T newVal )
{
Node<T> p = getNode( idx );
T oldVal = p.data;
p.data = newVal;
return oldVal;
}
//获取索引处的节点
private Node<T> getNode( int idx )
{
return getNode( idx, 0, size( ) - 1 );
}
// //获取索引处的节点,索引限制在lower和upper之间
private Node<T> getNode( int idx, int lower, int upper )
{
Node<T> p;
if( idx < lower || idx > upper )
throw new IndexOutOfBoundsException("getNode index: " + idx + "; size: " + size( ));
if( idx < size( ) / 2 )
{
p = begin.next;
for( int i = 0; i < idx; i++ )//从最前面开始往后遍历
p = p.next;
}
else
{
p = end;
for( int i = size( ); i > idx; i-- )//从最后面开始往前遍历
p = p.prev;
}
return p;
}
//删除索引处的节点
public T remove( int idx )
{
return remove( getNode( idx ) );
}
//删除节点p
private T remove( Node<T> p )
{
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
return p.data;
}
public String toString( )
{
StringBuilder sb = new StringBuilder( "[ " );
for( T x : this )
sb.append( x + " " );
sb.append( "]" );
return new String( sb );
}
public java.util.Iterator<T> iterator( )
{
return new LinkedListIterator( );
}
private class LinkedListIterator implements java.util.Iterator<T>
{
private Node<T> current = begin.next;
private boolean okToRemove = false;
public boolean hasNext( )
{
return current != end;
}
public T next( )
{
if( !hasNext( ) )
throw new java.util.NoSuchElementException( );
T nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
public void remove( )
{
if( !okToRemove )
throw new IllegalStateException( );
MyLinkedList.this.remove( current.prev );
okToRemove = false;
}
}
private static class Node<T>
{
public Node( T d, Node<T> p, Node<T> n )
{
data = d; prev = p; next = n;
}
public T data;
public Node<T> prev;
public Node<T> next;
}
}
public class TestLinkedList
{
public static void main( String [ ] args )
{
MyLinkedList<Integer> lst = new MyLinkedList<Integer>( );
for( int i = 0; i < 10; i++ )
lst.add( i );
for( int i = 20; i < 30; i++ )
lst.add( 0, i );
lst.remove( 0 );
lst.remove( lst.size( ) - 1 );
System.out.println( lst );
java.util.Iterator<Integer> itr = lst.iterator( );
while( itr.hasNext( ) )
{
itr.next( );
itr.remove( );
System.out.println( lst );
}
}
}
运行结果:
[ 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 23 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 22 21 20 0 1 2 3 4 5 6 7 8 ]
[ 21 20 0 1 2 3 4 5 6 7 8 ]
[ 20 0 1 2 3 4 5 6 7 8 ]
[ 0 1 2 3 4 5 6 7 8 ]
[ 1 2 3 4 5 6 7 8 ]
[ 2 3 4 5 6 7 8 ]
[ 3 4 5 6 7 8 ]
[ 4 5 6 7 8 ]
[ 5 6 7 8 ]
[ 6 7 8 ]
[ 7 8 ]
[ 8 ]
[ ]
下载源码:
分享到:
相关推荐
JAVA实现链表_双向链表
NULL 博文链接:https://zhanhao.iteye.com/blog/1137409
双端链表和双向链表Java代码
用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
通过java实现的双向链表,及反转功能,可能对面试有用哦
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
操作包括: 1. 在头部添加结点 2. 在尾部添加结点 3. 遍历 4. 逆置 5. 删除
用java实现双向链表的完整操作,主要用到内部类实现。
自定义的双向链表 博文链接:https://hiliangliang1130-126-com.iteye.com/blog/1144023
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字...为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。
相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
Java 有序 非循环 双向 链表 算法 实例
主要介绍了Java实现双向链表(两个版本)的相关资料,需要的朋友可以参考下
二叉树转换为双向链表 通过随机创建二叉排序树测试二叉树转换为双向链表是否正确 http://blog.csdn.net/ssuchange/article/details/17383625
2022年Java语言中链表和双向链表Java教程.docx
在双向链表上实现快速排序的递归算法 输入的形式:元素个数、元素都为整型。 输入值范围:元素个数为非负正整数,需要排序的元素都为整型。 输出的形式:排序前的元素序列和排序后的元素序列。 程序的功能:对用户...
已知N个人(以编号1,2,3...n分别表示)围成一个圈。 从编号为K的人开始报数,数到M的那个人出列,他的下一个人又从1开始报数,依照此规律重复下去,直到圆圈中的人全部出列。 问题:请打印出这N个的...双向链表实现的
Java算法实例-双向链表操作,封装性高,考试、学习都可使用
数据结构之双向链表的Java实现.doc
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...