【数据结构】模拟实现LinkedList

数据结构】模拟实现LinkedList"/>

【数据结构】模拟实现LinkedList

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 (head==null){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 (last==null){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 (index==0){addFirst(data);return;}//如果在最后一个位置插入 可以使用尾插法if (index==size()){addLast(data);return;}ListNode node = new ListNode(data);//判断要插入的下标是否合法if (index<0||index>size()){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 (head==null){return false;}ListNode cur = head;while (cur!=null){if (cur.val==key){return true;}cur = cur.next;}return false;
}

实现remove方法（删除第一次出现关键字为key的节点）

public void remove(int key){ListNode cur = head;while (cur!=null){if (cur.val==key){//删除头节点if (cur==head){head = head.next;if (head==null){//只有一个头节点cur.prev=null;}else {last=null;}}else {if (cur.next!=null){//删除中间节点cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//删除尾节点cur.prev.next=cur.next;last=last.prev;}}return;}else {cur=cur.next;}}
}

实现removeAllkey（删除所有值为key的节点）

public void removeAllKey(int key){ListNode cur = head;while (cur!=null){if (cur.val==key){//删除头节点if (cur==head){head = head.next;if (head==null){//只有一个头节点cur.prev=null;}else {last=null;}}else {if (cur.next!=null){//删除中间节点cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//删除尾节点cur.prev.next=cur.next;last=last.prev;}}cur=cur.next;}else {cur=cur.next;}}
}

实现clear方法（清除链表）

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