Ex1_3_31 双向链表DulLinkList
  1. import edu.princeton.cs.algs4.StdIn;
  2. import edu.princeton.cs.algs4.StdOut;
  4. public class DulLinkList<Item> {
  5.     private class DulNode {
  6.         Item item;
  7.         DulNode left;
  8.         DulNode right;
  9.     }
  11.     private DulNode head;
  12.     private DulNode tail;
  14.     private int size;
  17.     public int getSize() {
  18.         return size;
  19.     }
  21.     public boolean isEmpty() {
  22.         return head == null;
  23.     }
  25.     //从表头插入节点
  26.     public void headInsert(Item item) {
  27.         DulNode current = head;
  28.         head = new DulNode();
  29.         head.item = item;
  30.         if (isEmpty()) {
  31.             tail = head;
  32.         }//链表为空时head,tail指向一个节点
  33.         else {
  34.             head.right = current;
  35.         }
  36.         size++;
  37.     }
  38.     //从表尾插入节点
  39.     public void tailInsert(Item item) {
  40.         DulNode current = tail;
  41.         tail = new DulNode();
  42.         tail.item = item;
  43.         tail.left = current;
  44.         if (isEmpty()) {
  45.             head = tail;//tail = head错误,两个永远为null
  46.         }//链表为空时head,tail指向一个节点
  47.         else {
  48.             current.right = tail;
  49.         }
  50.         size++;
  51.     }
  52.     //从表头删除节点
  53.     public Item headDel() {
  54.         Item item = head.item;
  55.         head = head.right;
  56.         size--;
  57.         return item;
  58.     }
  59.     //从表尾删除节点
  60.     public Item tailDel() {
  61.         Item item = tail.item;
  62.         tail = tail.left;
  63.         size--;
  64.         return item;
  65.     }
  66.     //在指定节点前插入节点
  67.     public void beforeInsert(DulNode exist, Item item) {
  68.         DulNode dulNode = new DulNode();
  69.         dulNode.item = item;
  70.         if(exist.left == null) headInsert(item);
  71.         else{
  72.             exist.left.right = dulNode;
  73.             dulNode.left = exist.left;
  74.             exist.left = dulNode;
  75.             dulNode.right = exist;
  76.             size++;
  77.         }
  78.     }
  79.     //在指定节点后插入节点
  80.     public void afterInsert(DulNode exist, Item item){
  81.         DulNode dulNode = new DulNode();
  82.         dulNode.item = item;
  83.         if(exist.right == null) tailInsert(item);
  84.         else{
  85.             exist.right.left = dulNode;
  86.             dulNode.right = exist.right;
  87.             exist.right = dulNode;
  88.             dulNode.left = exist;
  89.             size++;
  90.         }
  91.     }
  92.     //删除指定节点
  93.     public Item del(DulNode dulNode){
  94.         Item item = dulNode.item;
  95.         if (dulNode == head) headDel();
  96.         else if(dulNode == tail) tailDel();
  97.         else{
  98.             dulNode.left.right = dulNode.right;
  99.             dulNode.right.left = dulNode.left;
  100.         }
  101.         return item;
  102.     }
  104.     //测试用例
  105.     public static void main(String[] args){
  106.         DulLinkList linkList = new DulLinkList();
  108.         while(!StdIn.isEmpty()){
  109.             String s = StdIn.readString();
  110.             linkList.tailInsert(s);
  111.         }
  112.         linkList.beforeInsert(linkList.head,-1);
  113.         StdOut.println(linkList.size + " elements");
  114.         StdOut.println(linkList.head.item);
  115.         StdOut.println(linkList.tail.item);
  116.     }
  117. }

要点:

  1. 插入节点时,当链表为空,head,tail都指向新节点,注意
  1. //实例化表头
  2.  DulNode current = head;
  3.         head = new DulNode();
  4.         head.item = item;
  5.         if (isEmpty()) {
  6.             tail = head;
  7.         }//链表为空时head,tail指向一个节点
  8.         else {
  9.             head.right = current;
  10.         }
  11. //实例化表尾
  12. DulNode current = tail;
  13.         tail = new DulNode();
  14.         tail.item = item;
  15.         tail.left = current;
  16.         if (isEmpty()) {
  17.             head = tail;//tail = head错误,两个永远为null
  18.         }//链表为空时head,tail指向一个节点
  19.         else {
  20.             current.right = tail;
  21.         }

将实例化的节点赋值给空引用,才能让tail与head都指向实例化节点,若赋值顺序颠倒,两节点用为null

  1. 注意在指定节点前/后插入节点,要判断指定节点是否是头/尾结点,否则会产生空指针错误
  2. 插入节点时连接顺序不同
  1. //前插
  2. if(exist.left == null) headInsert(item);
  3.         else{
  4.             exist.left.right = dulNode;
  5.             dulNode.left = exist.left;
  6.             exist.left = dulNode;
  7.             dulNode.right = exist;
  8.             size++;
  9.         }
  10. //后插
  11. if(exist.right == null) tailInsert(item);
  12.         else{
  13.             exist.right.left = dulNode;
  14.             dulNode.right = exist.right;
  15.             exist.right = dulNode;
  16.             dulNode.left = exist;
  17.             size++;
  18.         }

在指定节点前插入节点时:在AB中指定B插入C,则先连接A.right和B.left再连接BC

在指定节点后插入节点时:在AB中指定A插入C,则先连接C.right和B.left再连接AC