引言
在之前的博文中,我简单的向大家分享了一些链表相关的知识及一些面试题,如果感兴趣的老铁可以去瞧瞧!今天给大家带来双向链表以及带傀儡节点的双向链表的实现。认真看,每一步都有具体的来由和理解,希望对大家有所帮助!
详细步骤解析咋们边看代码边学习!
双向链表的实现
class ListNode{ public int val;//数值域 public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } } public class DoubleLinkedList { public ListNode head;//指向双链表的头节点 public ListNode last;//指向双链表尾巴节点 //打印链表--和打印单链表的方式一样 public void display(){ ListNode cur = this.head; while (cur!=null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //得到单链表的长度 public int size(){ int count = 0;//记录节点个数 ListNode cur = this.head; while (cur!=null) { count++; cur = cur.next; } return count; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode cur = this.head; while (cur!=null) { if(cur.val == key) {//如果cur.val等于key返回真 return true; }//否则继续往下走 cur = cur.next; } return false; } //头插法 public void addFirst(int data){ ListNode node = new ListNode(data);//new了个插入节点 if(head == null) {//如果插入时链表为空则,头和尾都指向新节点node this.head = node; this.last = node; }else { node.next = head; head.prev = node; this.head = node; } } //尾插法 public void addLast(int data){ ListNode node = new ListNode(data); if(this.head == null) { this.head = node; this.last = node; }else { this.last.next = node; node.prev = last; this.last = node; } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data){ ListNode node = new ListNode(data); if(index<0 || index>size()){ System.out.println("index位置不合法"); } if(index == 0) { addFirst(data); } if(index==size()){ addLast(data); } ListNode cur = searchIndex(index); node.next = cur.prev.next; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; } public ListNode searchIndex(int index) { ListNode cur = this.head;//创建个方法找到插入时cur的位置 while (index != 0) { cur = cur.next; index--; } return cur; } //删除第一次出现关键字为key的节点 //单链表中删除第一次出现的关键字需要找到关键字前驱 //双链表只需要直接找到这个节点 public void remove(int key){ ListNode cur = this.head; while (cur!=null) { if(cur.val == key) {//这里分两种情况 if(cur == head) {//1.cur等于头结点 head = head.next; head.prev = null;//手动置为空 }else {//2.cur不等于头结点 cur.prev.next = cur.next; if(cur.next!=null) { //中间位置 cur.next.prev = cur.prev; }else {//尾巴位置 last = last.prev; } } return; }else { cur = cur.next; } } } //删除所有值为key的节点 public void removeAllKey(int key){ ListNode cur = this.head; while (cur != null) { if (cur.val == key) { if (cur == head) { head = head.next; if (head != null) { head.prev = null; } else { last = null; } } else { cur.prev.next = cur.next; if (cur.next != null) { //中间位置 cur.next.prev = cur.prev; } else { last = last.prev; } } //return; } cur = cur.next; } } public void clear(){ while (head!=null) { ListNode curNext = head.next; head.next = null; head.prev = null; head = curNext; } last = null; } } 双向链表增删添改的实现
public class TestDemo { public static void main(String[] args) { DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.addLast(12); doubleLinkedList.addLast(13); doubleLinkedList.addLast(14); doubleLinkedList.addLast(15); doubleLinkedList.addLast(16); doubleLinkedList.display(); System.out.println("================="); doubleLinkedList.addIndex(3,99); doubleLinkedList.display(); } } 带傀儡节点的双向链表的实现
class ListNode{ public int val; public ListNode next; public ListNode prev; public ListNode(int val) { this.val = val; } } public class DoubleLinkedList {//带傀儡节点的双链表 public ListNode dummyHead;//虚拟节点 public ListNode last;//尾节点 public DoubleLinkedList() { this.dummyHead = new ListNode(-1);//傀儡节点 } //打印单链表 public void display() { ListNode cur = this.dummyHead.next; //引用cur代替head,head等于傀儡节点下一个节点 while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //得到单链表的长度 public int size() { int count = 0;//记录节点个数 ListNode cur = this.dummyHead.next; while (cur != null) { count++; cur = cur.next; } return count; } //头插法 public void addFirst(int data) { ListNode node = new ListNode(data); //第一次插入一个节点都没有的情况 if (this.dummyHead.next == null) { node.prev = dummyHead; this.dummyHead.next = node; this.last = node; return; } else { //新插入的节点和他前后节点连接 node.next = this.dummyHead.next; node.prev = this.dummyHead; this.dummyHead.next.prev = node; this.dummyHead.next = node; } } //尾插法 public void addLast(int data) { ListNode node = new ListNode(-1); //判断头节点是否为空 if (this.dummyHead.next == null && this.last.next == null) { this.dummyHead.next = node; node.prev = this.dummyHead; this.last = node; return; } else { this.last.next = node; node.prev = last; this.last = node; } } //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data) { ListNode node = new ListNode(data); if(index<0 || index>size()){ System.out.println("index位置不合法"); return; }else { if(index == 0) { addFirst(data); } if(index == size()) { addLast(data); }else { //中间位置的时候 ListNode cur = searchIndex(index); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; } } } //创建个方法找到cur的位置 public ListNode searchIndex(int index) { //先找到cur的位置 ListNode cur = this.dummyHead.next; while (index!=0) { cur = cur.next; index--; } return cur; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ ListNode cur = this.dummyHead.next; while (cur!=null) { if(cur.val == key) { return true; } cur = cur.next; } return false; } //删除第一次出现关键字为key的节点 //单链表中删除第一次出现的关键字需要找到关键字前驱 //双链表只需要直接找到这个节点 public void remove(int key){ ListNode cur = this.dummyHead.next; if(cur.val == key){//有两种情况 cur=head或者cur不等于head if(cur == this.dummyHead.next) {//cur==head时 this.dummyHead.next = this.dummyHead.next.next; this.dummyHead.next.next.prev = null; }else {//cur不等于head又有两种情况 //1.cur在中间位置2.cur在最后的位置 cur.prev.next = cur.next; //判断是不是最后一个节点 //要删除的节点不是最后一个节点 if(cur.next!=null){ cur.next.prev = cur.prev; }else { this.last = cur.prev; } } return; }else { cur = cur.next; } } //删除所有值为key的节点 public void removeAllKey(int key){ ListNode cur = this.dummyHead.next; while (cur!=null) { if(cur.val == key){ if(cur == this.dummyHead.next) { this.dummyHead.next = this.dummyHead.next.next; this.dummyHead.next.prev = null; }else { cur.prev.next = cur.next; //判断如果是最后一个节点 if(cur.next == null) { this.last = cur.prev; }else { cur.next.prev = cur.prev; } } } cur = cur.next; } } public void clear(){ ListNode cur = this.dummyHead.next; ListNode curNext = cur.next; while (cur!=null) { cur.prev = null; cur.next = null; cur = curNext; } this.dummyHead = null; this.last = null; } }