一.简介
物理上不一定连续，逻辑上连续
分类（共8种）：单向，双向，带头，不带头，循环，非循环
二.模拟实现
MyLinkedList类
package LinkedList; //无头单向不循环 public class MyLinkedList { class ListNode{ public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head;//链表头结点 //遍历打印 public void display(){ ListNode cur=head; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); } public int size(){ int cnt=0; ListNode cur=head; while(cur!=null){ cnt++; cur=cur.next; } return cnt; } //头插 public void addFirst(int val){ ListNode node=new ListNode(val); //插入节点时，先绑定后面的 node.next=head; head=node; } //尾插 public void addLast(int val){ ListNode node=new ListNode(val); //head为空 if(head==null){ head=node; return; } //head不为空 ListNode cur=head; while(cur.next!=null){ cur=cur.next; } cur.next=node; } //插入在指定位置的后面 public void addIndex(int index,int val){ ListNode node=new ListNode(val); //判断index位置是否合法 try{ checkIndex(index); }catch (IndexNotLegalException e){ e.printStackTrace(); } //index=0||index=size if(index==0) { addFirst(val); }else if(index==size()){ addLast(val); }else{ //找到index前一个位置 ListNode pre=findIndexSubOne(index); //插入连接 node.next= pre.next; pre.next=node; } } private void checkIndex(int index)throws IndexNotLegalException{ if(index<0||index>size()){ throw new IndexNotLegalException("index不合法！"); } } private ListNode findIndexSubOne(int index){ ListNode cur=head; int cnt=0; while(cnt!=index){ cur=cur.next; cnt++; } return cur; } public boolean containsValue(int val){ ListNode cur=head; while(cur!=null){ if(cur.val==val){ return true; } cur=cur.next; } return false; } //删除第一次出现的节点 public void remove(int val){ if(head==null){ return; } if(head.val==val){ head=head.next; return; } ListNode cur=head; while(cur.next!=null){ if(cur.next.val==val){ cur.next=cur.next.next; return; } cur=cur.next; } } //删除所有的关键字 public void removeAllKey(int val){ if(head==null){ return; } ListNode pre=head; ListNode cur=head.next; //判断，删除 while(cur!=null){ if(cur.val==val){ pre.next=cur.next; cur=cur.next; }else{ pre=cur; cur=cur.next; } } //判断头结点 if(head.val==val){ head=head.next; } } public void clear(){ //1 //head=null; //2 ListNode cur=head; while(cur!=null){ ListNode curN=cur.next; cur.next=null; cur=curN; } head=null; } }IndexNotLegalException异常
package LinkedList; public class IndexNotLegalException extends RuntimeException { public IndexNotLegalException(){ } public IndexNotLegalException(String msg){ System.out.println(msg); } }
