一 LinkedList
LinkedList的方法的实现
1.头插法
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;@Overridepublic void addFirst(int data) {ListNode node=new ListNode(data);ListNode cur=head;if (head==null) {head = last = cur;} else{node.next=head;head.prev=node;head=node;}}
}
2.尾插法
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;public void addLast(int data) {ListNode node=new ListNode(data);ListNode cur=head;if (head==null) {head = last = cur;} else{node.prev=last;last.next=node;last=node;}}
}
3.任意位置插入,第一个数据节点为0号下标
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}
public void addIndex(int index, int data) {ListNode node=new ListNode(data);int len=size();if(index<0 || index>len){return;}if(index==0){addFirst(data);}if(index==len){addLast(data);}ListNode cur=head;node.next=cur;node.prev=cur.prev;cur.prev.next=node;cur.prev=node;}
4.查找是否包含关键字key是否在链表当中
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;
public boolean contains(int key) {ListNode cur=head;while (head!=null){if(head.val==key){return true;}head=head.next;}return false;}
5.得到链表的长度
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;public int size() {ListNode cur=head;int count=0;while (head!=null){count++;head=head.next;}return count;}
6.打印链表
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;public void display() {ListNode cur=head;while (head!=null){System.out.println(head.val+" ");head=head.next;}}
7.删除第一次出现关键字为key的节点
删除中间部分
删除头
并且考虑只有一项的情况下
删除尾
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;public void remove(int key) {ListNode cur=head;while (cur!=null){if(cur.val==key){if(cur==head){head=head.next;if(head!=null) {head.prev=null;}}else {if(cur.next==null){cur.prev.next=null;last=last.prev;}else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}}return;}cur=cur.next;}}
}
8.删除所有值为key的节点
跟remove基本一样,删去return就行了,将整个链表检查一遍,删去全部的key
public void removeAllKey(int key) {ListNode cur=head;while (cur!=null){if(cur.val==key){if(cur==head){if(head!=null) {cur.next.prev = null;}}else {if(cur.next==null){cur.prev.next=null;last=last.prev;}else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}}}cur=cur.next;}}
9.清空链表
public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;public void clear() {ListNode cur=head;while (cur!=null){ListNode curN=cur.next;cur.prev=null;cur.next=null;cur=curN;}}
}
LinkedList方法的使用
public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();List<Integer> list=new LinkedList();linkedList.add(1);linkedList.addFirst(3);linkedList.addLast(6);ArrayList<Integer> list1=new ArrayList<>();list1.add(1);list1.add(2);list1.add(3);list1.add(4);linkedList.addAll(list1);System.out.println(linkedList);linkedList.remove(2);linkedList.get(3);linkedList.set(2,6);linkedList.contains(5);linkedList.size();linkedList.clear();}
LinkedList的遍历
1.for循环遍历
public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();linkedList.add(1);linkedList.addFirst(3);linkedList.addLast(6);for (int i = 0; i < linkedList.size(); i++) {System.out.println(linkedList.get(i)+" ");}}
2.foreach遍历
public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();linkedList.add(1);linkedList.addFirst(3);linkedList.addLast(6);
for (Integer x:linkedList) {System.out.print(x+" ");}}
}
3.迭代器
Iterator
public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();linkedList.add(1);linkedList.addFirst(3);linkedList.addLast(6);Iterator<Integer> iterator=linkedList.iterator();while (iterator.hasNext()){System.out.print(iterator.next());}
ListIterator
1.按顺序打印
public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();linkedList.add(1);linkedList.addFirst(3);linkedList.addLast(6);ListIterator<Integer> it=linkedList.listIterator();while (it.hasNext()){System.out.println(it.next()+" ");}
2.逆序打印
public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();linkedList.add(1);linkedList.addFirst(3);linkedList.addLast(6);ListIterator<Integer> it1=linkedList.listIterator();while (it1.hasPrevious()){System.out.println(it1.previous()+" ");}
}
注: ListIterator可以当作迭代器的原因是,它是Iterator的子类,专门用来打印List类的。
ArrayList和LinkedList的区别
当你进行查找时,我建议你选择ArrayList,因为LinkedList访问任意元素需要从头或尾遍历链表,时间复杂度为 O(n),ArrayList可以通过索引直接访问任意元素,时间复杂度是 O(1)。
当我们经常使用插入等功能,可以使用LinkedList,如果在末尾插入或删除元素,效率较高(时间复杂度 O(1)),ArrayList需要移动大量元素,因此效率较低(时间复杂度 O(n))。
希望能对大家有所帮助!!!!