一 链表
1.. ArrayList的缺陷（LinkedList的优点）
在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。
2.什么是链表
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。我们可以把链表想象成火车的车厢连接在一起。
3.链表的八种形式
最常用的为单向链表
还有双向链表，带头或者不带头链表，循环或者非循环链表
4.链表的实现
public interface IList {//头插法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();public void display();}1.头插法
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public void addFirst(int data) {ListCode node=new ListCode(data);node.next=head;head=node;}
}2.尾插法
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public void addLast(int data) {ListCode cur=head;ListCode node=new ListCode(data);if(cur==null){head=node;return;}while (cur!=null){cur=cur.next;}cur.next=node;}
}3.得到单链表的长度
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public int size() {int len=0;ListCode cur=head;while (cur!=null){len++;cur=cur.next;}return len;}
}4.任意位置插入,第一个数据节点为0号下标
public class IllegalException extends RuntimeException{public IllegalException(){}public IllegalException(String mas){super(mas);}
}
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public void addIndex(int index, int data) throws IllegalException{try {int len=size();if(index<0 || index>len){throw new IllegalException("pos位置不合法");}if(len==0){addFirst(data);}if (index==len-1){addLast(data);}ListCode node=new ListCode(data);ListCode cur=head;while (index!=0){cur=cur.next;index--;}node.next=cur.next;cur.next=node;}catch (IllegalException e){e.printStackTrace();System.out.println("pos位置不合法");}}
}5.查找是否包含关键字key是否在单链表当中
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public boolean contains(int key) {ListCode cur=head;while (cur!=null){if (cur.val==key){return true;}}return false;}
}6.删除第一次出现关键字为key的节点
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public void remove(int key) {if (head==null){return;}if(head.val==key){return;}ListCode cur=findNodeOfKey(key);if(cur==null){return;}ListCode del=cur.next;cur.next=del.next;}public ListCode findNodeOfKey(int key){ListCode cur=head;while (cur.next!=null){if(cur.next.val==key){return cur;}cur=cur.next;}return null;}
}7. 删除所有值为key的节点
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public void removeAllKey(int key) {if(head==null){return;}ListCode cur=head.next;ListCode pre=head;while (cur!=null){if(cur.val==key){pre.next=cur.next;cur=cur.next;}else {pre=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}
}8.清空单链表
public class MyArrayList implements IList {static class ListCode {public int val;public ListCode next;public ListCode(int val) {this.val = val;}}public ListCode head;public void clear() {ListCode cur=head;while (cur.next!=null){ListCode cun1=cur;cur.next=null;cur=cun1.next;}head=null;}
}希望能对大家有所帮助！！！！
