【数据结构】链表（2）

 【LinkedList的模拟实现】

这是java中的一个集合类，可以当成链表来使用，作为链表时，它视为包含三个域，是一个双向链表

【构建LinkedList框架】

public class MyLinkedList
{static class ListNode{public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val){this.val = val;}}public ListNode head;//标志头节点public ListNode last;//标志尾节点
}

【得到双向链表的长度】

 public int size(){int count = 0;ListNode cur = head;while(cur != null){count++;cur = cur.next;}return count;}

【打印双向链表的值】

 public void display(){ListNode cur = head;while(cur != null){System.out.println(cur.val + " ");cur = cur.next;}System.out.println();}

【查找关键字key是否在链表中】

public boolean containsKey(int key){ListNode cur = head;while(cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}

【头插法】

1.链表不为null时，node的next域中存放head指向的节点地址（node.next = head）

2.head的prev域中存放node指向的节点地址（head.prev = node）

3.head指向node(head = node)

 public void addFirst(int data){ListNode node = new ListNode(data);if(head == null)//判断是否是首次插入节点{head = last = node;}else{node.next = head;head.prev = node;head = node;}}

【尾插法】

1.链表不为null时，last所指向节点的next域中存放node指向的节点地址（last.next = node）

2.node的prev域中存放last指向的节点地址（node.prev = last）

3.last指向node（last = node ）(或者last = last.next)

 public void addLast(int data){ListNode node = new ListNode(data);if(head == null)//判断是否是首次插入节点{head = last = node;}else{last.next = node;node.prev = last;last = node; //last = last.next;}}

【任意位置插入】

单链表时如果想插2位置，需要找到2的前一个节点，相当于要定义一个cur，走到目标位置的前一个节点，但双向链表是可以通过prev直接知道前一个节点的地址的

1.直接记录index位置的节点cur

2.node的next域被设置为cur指向的节点地址（node.next = cur）

3.cur的前驱节点中的next域被设置为cur指向的节点地址（cur.prev.next = node）

4.node的prev域被设置为cur前驱中所存放的节点地址（node.prev = cur.prev）

5.cur的prev域被设置为node指向的节点地址(cur.prev = node)

 public void addIndex(int index, int data){//1.判断index的合法性try {checkIndex(index);} catch (InterruptedException e) {e.printStackTrace();}//2.index == 0 || index == size()if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}//3.找到index位置ListNode cur = findIndex(index);ListNode node = new ListNode(data);//4.进行链接node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}private ListNode findIndex(int index)//找到index位置{ListNode cur = head;while(index != 0){cur = cur.next;index--;}return cur;}private void checkIndex(int index) throws InterruptedException//检查index是否合法{if(index < 0 || index > size()){throw new IndexNotLegalException("index不合法");}}

【删除关键字为key的节点】

1.找到关键字key所在的节点cur

2.cur前驱节点的next域被设置为cur的next域中所存放的节点地址（cur.prev.next = cur.next）

3.cur后继节点的prev域被设置为cur的prev域中所存放的节点地址(cur.next.prev = cur.prev)

public void remove(int key){ListNode cur = head;while(cur.next != null){if(cur.val == key){if(cur == head)//处理头节点{head = head.next;if(head != null){head.prev = null;}else//head为null，证明只有一个节点{last = null;}}else{cur.prev.next = cur.next;if (cur.next == null)//处理尾节点{last = last.next;} else {cur.next.prev = cur.prev;return;}}}cur = cur.next;}}

【清空链表】

public void clear(){ListNode cur = head;while(cur != null){ListNode curN = cur.next;cur.prev = null;cur.next = null;cur = curN;}head = last =  null;}