java单链表的基本操作 单链表练习题.zip

package MyLinkedList实现; import class自己实现链表.MyIterator; //利用 双向链表 实现基本操作 public class MyLinkedList implements MyList { public MyListNode head; public MyListNode last; public MyLinkedList() { //MyLinkedList对象 的无参构造方法 head=null; last=null; } @Override public boolean add(String e) { //O(1) //1.把e先装入结点中 MyListNode node=new MyListNode(e); //2.将结点尾插 考虑链表为空：头结点与尾结点均指向插入的结点 链表不为空 if(head==null) { head=node; last=node; }else { node.prev=last; last.next=node; last=node; } return true; } @Override public void add(int index, String e) { //判断下标合法性 if(index<0 || index>size()) { throw new ArrayIndexOutOfBoundsException("下标不合法！"); } MyListNode node=new MyListNode(e); //index=0即头插，需要单独处理，否则将于index=1的结果相同 if(index==0) { //头插 if(head!=null) { //head不为空即链表中至少有一个元素 head.prev不会报错 node.next=head; head.prev = node; head=node; }else {//非空头插 head=node; last=node; } return; } //index=size即尾插，单独处理会更方便 if(index==size()) { add(e); return; } //1.先找到待插入位置的前驱结点，从head开始，需要向后跳index-1步 MyListNode prev=head; for(int i=0;i<index-1;i++) { prev=prev.next; } MyListNode next=prev.next; //插入node node.prev=prev; node.next=next; prev.next=node; next.prev=node; } @Override public String remove(int index) { if(index<0 || index>=size()) { throw new ArrayIndexOutOfBoundsException("下标不合法！"); } //可能的情况 //index==0 头删 //index==size()-1 尾删 //index!=0 && index!=size()-1 中间删 //size()==1 等价于head.next==null 等价于prev.next==null if(size()==1) { String e=head.val; head=null; last=null; return e; }else if(index==0) { //元素个数大于1的头删 String e=head.val; head=head.next; head.prev=null; return e; }else if(index==size()-1) { //元素个数大于1的尾删 String e=last.val; last=last.prev; last.next=null; return e; }else { //中间删 MyListNode delete=head; for(int i=0;i<index;i++) { delete=delete.next; } String e=delete.val; MyListNode prev=delete.prev; MyListNode next=delete.next; prev.next=next; next.prev=prev; return e; } } @Override public boolean remove(String e) { int index=indexOf(e); if(index<0) { return false; } remove(index); return true; } @Override public String get(int index) { if(index<0 || index>=size()) { throw new ArrayIndexOutOfBoundsException("下标不合法！"); } MyListNode cur=head; for(int i=0;i<index;i++) { cur=cur.next; } return cur.val; } @Override public String set(int index, String e) { if(index <0 || index>size()) { throw new ArrayIndexOutOfBoundsException("下标不合法！"); } MyListNode cur=head; for(int i=0;i<index;i++) { cur=cur.next; } String old=cur.val; cur.val=e; return old; } @Override public boolean contains(String e) { return indexOf(e)>=0; } @Override public int indexOf(String e) { //从头查找元素e所在的下标 int i=0; for(MyListNode cur=head;cur!=null;cur=cur.next) { if(cur.val.equals(e)) { return i; } i++; } return -1; } @Override public int lastIndexOf(String e) { //从尾查找元素e所在的下标 int i=size()-1; for(MyListNode cur=last;cur!=null;cur=cur.prev) { if(cur.val.equals(e)) { return i; } i--; } return -1; } @Override public void clear() { head=null; last=null; } @Override public int size() { int count=0; for(MyListNode cur=head;cur!=null;cur=cur.next) { count++; } return count; } @Override public boolean isEmpty() { return size()==0; } @Override public MyIterator iterator() { return null; } @Override public String toString() { //String是一个不可变对象，反复修改String会生成新的String对象 //用StringBuilder改善这个问题 StringBuilder sb=new StringBuilder("["); for(MyListNode cur=head;cur!=null;cur=cur.next) { sb.append(cur.val); if(cur!=last) { sb.append(","); } } sb.append("]"); return sb.toString(); //String是一个不可变对象，反复修改String会生成新的String对象 //用StringBuilder改善这个问题 // String ans="["; // // MyListNode cur=head; // while (cur!=null) { // ans=ans+","+cur.val; // //String是一个不可变对象，反复修改String会生成新的String对象 // //用StringBuilder改善这个问题 // cur=cur.next; // } // ans=ans+"]"; // return ans; } }