网站建设网络推广加盟,虚拟产品网站,宣传彩页设计,数学wordpress博客LinkedList是双向链表结构可以适用于任意插入场景下的插入和删除#xff0c;效率较高#xff0c;时间复杂度为O(1)。
模拟实现
public class MyLinkedList {static class ListNode{private int val;//值域private ListNode prev;//前驱private ListNode next;//后继public …LinkedList是双向链表结构可以适用于任意插入场景下的插入和删除效率较高时间复杂度为O(1)。
模拟实现
public class MyLinkedList {static class ListNode{private int val;//值域private ListNode prev;//前驱private ListNode next;//后继public ListNode(int val) {this.val val;}}public ListNode head;//双向链表的头节点public ListNode last;//双向链表的尾节点
}LinkedList常用方法
//头插法
public void addFirst(int data)//尾插法
public void addLast(int data)//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data)//查找是否包含关键字key是否在单链表当中
public boolean contains(int key)//删除第一次出现关键字为key的节点
public void remove(int key)//删除所有值为key的节点
public void removeAllKey(int key)//得到链表的长度
public int size()//清空链表
public void clear()实现addFirst方法头插法
public void addFirst(int data){ListNode node new ListNode(data);//如果链表为空 插入的元素就是头节点和尾节点if (headnull){head node;last node;}else {node.next head;//使node的后继是现在的头节点head.prev node;//使现在的头节点的前驱是nodehead node;//让node成为新的头节点}
}实现addList方法尾插法
public void addLast(int data){ListNode node new ListNode(data);//和头插一样if (lastnull){head node;last node;}else {last.next node;//使现在尾节点的后继为nodenode.prev last;//使node的前驱为现在的尾节点last last.next;//让node成为尾节点}
}实现size方法求链表长度
public int size(){ListNode cur head;int count 0;while (cur!null){count;cur cur.next;}return count;
}实现addIndex方法在任意位置插入元素
public void addIndex(int index,int data){//插入的位置如果为0 可以使用头插法if (index0){addFirst(data);return;}//如果在最后一个位置插入 可以使用尾插法if (indexsize()){addLast(data);return;}ListNode node new ListNode(data);//判断要插入的下标是否合法if (index0||indexsize()){System.out.println(index 不合法index);return;}ListNode cur head;//让cur走到要插入的位置while (index!0){cur cur.next;index--;}node.next cur;cur.prev.next node;node.prev cur.prev;cur.prev node;
}实现contains方法查找是否包含关键字key是否在单链表当中
public boolean contains(int key){if (headnull){return false;}ListNode cur head;while (cur!null){if (cur.valkey){return true;}cur cur.next;}return false;
}实现remove方法删除第一次出现关键字为key的节点
public void remove(int key){ListNode cur head;while (cur!null){if (cur.valkey){//删除头节点if (curhead){head head.next;if (headnull){//只有一个头节点cur.prevnull;}else {lastnull;}}else {if (cur.next!null){//删除中间节点cur.prev.nextcur.next;cur.next.prevcur.prev;}else {//删除尾节点cur.prev.nextcur.next;lastlast.prev;}}return;}else {curcur.next;}}
}实现removeAllkey删除所有值为key的节点
public void removeAllKey(int key){ListNode cur head;while (cur!null){if (cur.valkey){//删除头节点if (curhead){head head.next;if (headnull){//只有一个头节点cur.prevnull;}else {lastnull;}}else {if (cur.next!null){//删除中间节点cur.prev.nextcur.next;cur.next.prevcur.prev;}else {//删除尾节点cur.prev.nextcur.next;lastlast.prev;}}curcur.next;}else {curcur.next;}}
}实现clear方法清除链表
public void clear(){ListNode cur head;while (cur!null){ListNode curNew cur.next;cur.prevnull;cur.nextnull;cur curNew;}headnull;lastnull;
}
