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;
}
}