本文共 2203 字,大约阅读时间需要 7 分钟。
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点
下面直接来看实现:
/** *双向链表实现(先进后出)
* @author white * @version $Id: MyLinkedList, v 0.1 2016/9/21 0021 下午 8:32 white Exp $ */public class MyLinkedList{ /** 栈顶元素 */ private Node first; /** 栈底元素 */ private Node last; /** 链表大小 */ private int size = 0; /** 双向链表结构 */ private class Node { T item; Node next; Node prev; } /** * 链表是否为空 * @return */ public boolean isEmpty() { return size == 0; } /** * 将元素压入栈顶 * @param item */ public void push(T item) { if (size == 0) { first = new Node(); first.item = item; last = first; size++; } else if (size > 0) { Node oldFirst = first; first = new Node(); first.item = item; first.next = oldFirst; oldFirst.prev = first; last = oldFirst; size++; } } /** * 取出链表的第一个元素 * @return */ public T pop() { if (size == 0) { throw new ArrayIndexOutOfBoundsException(); }else if (size == 1){ Node oldFirst = first; first = null; size--; return oldFirst.item; }else { Node oldFirst = first; first = first.next; first.prev = null; size--; return oldFirst.item; } } /** * 取栈深度 * @return */ public int size() { return size; }}
调用以下方法来查看结果:
public void test() { MyLinkedListmyLinkedList = new MyLinkedList (); System.out.println("cosSize:" + myLinkedList.size()); for (int i = 0; i < 15; i++) { myLinkedList.push("aaa" + i); } System.out.println("initSize:" + myLinkedList.size()); for (int i = 0; i < 15; i++) { System.out.println(myLinkedList.pop()); } System.out.println("popSize:" + myLinkedList.size()); }
输出结果:
cosSize:0initSize:15aaa14aaa13aaa12aaa11aaa10aaa9aaa8aaa7aaa6aaa5aaa4aaa3aaa2aaa1aaa0popSize:0
如有疑问,欢迎提出。
我的博客:blog.scarlettbai.com
转载地址:http://tesni.baihongyu.com/