当前位置:首页 > 开发 > 编程语言 > Java > 正文

双向链表(java实现)

发表于: 2012-08-21   作者:128kj   来源:转载   浏览:
摘要: 代码来自教科书。 public class MyLinkedList<T> implements Iterable<T> { private int theSize; private Node<T> begin;//头指针,哑的,第一个数据的前面 private Node<T> end;//尾指针,哑的,最后一个
代码来自教科书。
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实现)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
public class DoublyLinkList { private class Data{ private Object obj; private Data left = nul
线性表的Java实现--链式存储(双向链表) 有了单向链表的基础,双向链表的实现就容易多了。 双向链
链表学习--双向链表实现 今天学习了链表的数据结构。他的主要思路为: 1. 他访问数据的方式不是数组
直接进入主题,要想自己构建一个双向链表就得知道双向链表的构成,既然是链表,很容易让人联想到链
概要 线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成的有限序列。本章先介绍线性
链表是一种重要的数据结构,应用的非常广泛。链表分为单向链表与双向链表,一般的实现就是在结构体
先来看一下双向链表和双向循环链表的逻辑结构: 下面我们将用c/c++语言实现双向循环链表: #include
数据结构 双向链表表示和实现 参考代码如下: /* 名称:双向链表表示和实现 编译环境:VC++6.0 日期
一、双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双
一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号