【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;
}