注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

等待机遇

这个世界上没有人知道自己到底想要什么,就等着别人来告诉他们。

 
 
 

日志

 
 

JAVA实现双向链表  

2014-03-12 18:36:48|  分类: Java |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

其实java.util.LinkedList就是一个双链表:

public class DoubleLinkedList
{
  // 节点类Node

  private static class Node
  {
    Object value;
    Node prev = this;
    Node next = this;

    Node(Object v)
    {
      value = v;
    }

    public String toString()
    {
      return value.toString();
    }
  }
  private Node head = new Node(null); // 头节点
  private int size; // 链表大小
  // 以下是接口方法

  public boolean addFirst(Object o)
  {
    addAfter(new Node(o), head);
    return true;
  }

  public boolean addLast(Object o)
  {
    addBefore(new Node(o), head);
    return true;
  }

  public boolean add(Object o)
  {
    return addLast(o);
  }

  public boolean add(int index, Object o)
  {
    addBefore(new Node(o), getNode(index));
    return true;
  }

  public boolean remove(int index)
  {
    removeNode(getNode(index));
    return true;
  }

  public boolean removeFirst()
  {
    removeNode(head.next);
    return true;
  }

  public boolean removeLast()
  {
    removeNode(head.prev);
    return true;
  }

  public Object get(int index)
  {
    return getNode(index).value;
  }

  public int size()
  {
    return size;
  }

  public String toString()
  {
    StringBuffer s = new StringBuffer("[");
    Node node = head;
    for (int i = 0; i < size; i++)
    {
      node = node.next;
      if (i > 0)
        s.append(", ");
      s.append(node.value);
    }
    s.append("]");
    return s.toString();
  }
  //以下是实现方法

  private Node getNode(int index)
  {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException();
    Node node = head.next;
    for (int i = 0; i < index; i++)
      node = node.next;
    return node;
  }

  private void addBefore(Node newNode, Node node)
  {
    newNode.next = node;
    newNode.prev = node.prev;
    newNode.next.prev = newNode;
    newNode.prev.next = newNode;
    size++;
  }

  private void addAfter(Node newNode, Node node)
  {
    newNode.prev = node;
    newNode.next = node.next;
    newNode.next.prev = newNode;
    newNode.prev.next = newNode;
    size++;
  }

  private void removeNode(Node node)
  {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
    size--;
  }
}
//有些地方还可以优化,比如查找时可以判断索引是否大于size的一半,如果是的话,就从另一头开始迭代。

//可以用这个类测试一下:

public class Test
{
  public static void main(String[] args)
  {
    DoubleLinkedList dll = new DoubleLinkedList();
    //添加
    dll.add("张曼玉");
    dll.add("钟楚红");
    dll.add("刘嘉玲");
    System.out.println(dll);

    //添加到最前
    dll.addFirst("林青霞");
    System.out.println(dll);

    //添加到最后,同添加
    dll.addLast("梅艳芳");
    System.out.println(dll);

    //添加到指定位置
    dll.add(4, "王祖贤");
    System.out.println(dll);

    //移除最前的
    dll.removeFirst();
    System.out.println(dll);

    //移除最后的
    dll.removeLast();
    System.out.println(dll);

    //移除指定位置上的
    dll.remove(2);
    System.out.println(dll);

    //返回指定位置上的元素
    System.out.println(dll.get(1));

  }
}
输出:
[张曼玉, 钟楚红, 刘嘉玲]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲, 梅艳芳]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲, 王祖贤, 梅艳芳]
[张曼玉, 钟楚红, 刘嘉玲, 王祖贤, 梅艳芳]
[张曼玉, 钟楚红, 刘嘉玲, 王祖贤]
[张曼玉, 钟楚红, 王祖贤]
钟楚红

  评论这张
 
阅读(290)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017