519
数据结构之链表
数组的两大缺点：
1。若改变数组的大小就要创建一个新的数组，并需要从原数组复制所有的数据到新的数组
2。数组元素在内存中依次顺序存储，这意味着向数组插入一项要移动数组中的其他元素
因此，我们使用链式结构，链式结构是存储数据的结点以及指向其他节点的指针的集合。如此一来，节点可以位于内存的任意位置，而且从一个节点到另一个节点的传递可以通过在结构中存储节点间引用来实现。
一。单向链表
1。链表：
如果一个节点包含指向另一个节点的数据值，那么多个节点可以连接成一串，只通过一个变量访问整个节点序列，这样的节点序列称为链表（linked list）
2。单向链表：
如果每个节点仅包含其指向后继节点的引用，这样的链表称为单向链表。
一个整型单向链表的实现：
package com.sohu.blog.denns_zane.list;
/** */ /** 
* @author dennis * @Description 整型单向链表节点
*/ public class IntSLLNode 
{ public int info; // 用户信息 public IntSLLNode next; // 下一个节点，自引用 
/** */ /** * @param info * @param next
*/ public IntSLLNode( int info, IntSLLNode next) { this .info = info; this .next = next; } /** */ /** * @param info */ public IntSLLNode( int info) { this (info, null ); } } /** */ /** * */ package com.sohu.blog.denns_zane.list; /** */ /** * @author dennis * desc: 整型单向链表 */ public class IntSLList { protected IntSLLNode head, tail; public IntSLList() { head = tail = null ; } public boolean isEmpty() { return head == null ; } /** */ /** * @description 增加新节点，并设置它的next为原head * @param el */ public void addToHead( int el) { head = new IntSLLNode(el, head); if (tail == null ) tail = head; } /** */ /** * @description 增加新节点，并设置原tail的next为新节点 * @param el */ public void addToTail( int el) { if ( ! isEmpty()) { tail.next = new IntSLLNode(el); tail = tail.next; } else { head = tail = new IntSLLNode(el); } } public int deleteFromHead() { if (head == null ) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null ; else head = head.next; return el; } public int deleteFromTail() { if (head == null ) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null ; else { IntSLLNode temp; for (temp = head; temp.next != null && temp.next != tail; temp = temp.next) tail = temp; System.out.println(tail.info); tail.next = null ; } return el; } public void printAll() { for (IntSLLNode temp = head; temp != null ; temp = temp.next) System.out.print(temp.info + " " ); } public boolean isInList( int el) { for (IntSLLNode temp = head; temp != null ; temp = temp.next) { if (temp.info == el) return true ; } return false ; } /** */ /** * @param el */ public void delete( int el) { if ( ! isEmpty()) { if (head == tail && head.info == el) head = tail = null ; else if (head.info == el) head = head.next; else { IntSLLNode pred, temp; // pred为找的节点的前一节点，temp即为找到的节点 for (pred = head, temp = head.next; temp != null ; pred = pred.next, temp = temp.next) { if (temp.info == el) { pred.next = temp.next; // 前一节点的next设置为当前节点的next if (temp == tail) tail = pred; } } } } } } 二。双向链表
一个整型双向链表的实现：
/** *//** * */package com.sohu.blog.denns_zane.list;/** *//** * @author dennis desc:双向链表节点 */public class IntDLLNode { public int info; public IntDLLNode prev, next; /** *//** * @param info * @param prev * @param next */ public IntDLLNode(int info, IntDLLNode next, IntDLLNode prev) { super(); this.info = info; this.prev = prev; this.next = next; } public IntDLLNode(int info) { this(info, null, null); }}/** *//** * */package com.sohu.blog.denns_zane.list;/** *//** * @author dennis * */public class IntDLList { private IntDLLNode head, tail; public IntDLList() { head = tail = null; } public boolean isEmpty() { return head == null; } public void addToHead(int el) { if (head == null) head = new IntDLLNode(el); else { head = new IntDLLNode(el, head, null); head.next.prev = head; } if (tail == null) tail = head; } public void addToTail(int el) { if (!isEmpty()) { tail = new IntDLLNode(el, null, tail); tail.prev.next = tail; } else head = tail = new IntDLLNode(el); } public int removeFromTail() { if (head == null) throw new NullPointerException(); int el = tail.info; if (head == tail) head = tail = null; else { tail = tail.prev; tail.next = null; } return el; } public int removeFromHead() { if (head == null) throw new NullPointerException(); int el = head.info; if (head == tail) head = tail = null; else { head = head.next; head.prev = null; } return el; } public boolean isInList(int el) { if (head == null) return false; IntDLLNode temp; for (temp = head; temp != null; temp = temp.next) { if (temp.info == el) { return true; } } return false; } public void delete(int el) { if (head == null) throw new NullPointerException(); IntDLLNode temp; for (temp = head; temp != null; temp = temp.next) { if (temp.info == el) { if (temp == head) { head.next.prev = null; head = head.next; } else temp.prev.next = temp.next; } } } public void printAll() { IntDLLNode temp;