Java：数据结构-LinkedList和链表（2）

一 LinkedList

LinkedList的方法的实现

1.头插法

java">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.尾插法

java">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号下标

java">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是否在链表当中

java">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.得到链表的长度

java">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.打印链表

java">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的节点

删除中间部分

删除头

并且考虑只有一项的情况下

删除尾

java">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

java">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.清空链表

java">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方法的使用

java">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循环遍历

java">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遍历

java">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

java">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.按顺序打印

java">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.逆序打印

java">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类的。