数据结构篇02、链表，2024最新Android面试笔试题目分享_Android

return size;
}

// 返回链表是否为空
public boolean isempty(){
return size == 0;
}
、、、
}

2、往链表中添加元素

add(int index, e e)函数表示往索引index处添加元素e；其实在链表中一般没有这种需求，我们只是练习用；首先通过一个for循环找到index索引的节点，然后new一个节点插入进去即可；时间复杂度为o(n);

addfirst表示往链表头添加元素，因此时间复杂度为o(1);

addlast表示往链表尾添加元素，因此时间复杂度为o(n);这里注意一下，java的util库中linkedlist往链表尾添加元素的时间复杂度为o(1),因为它是维护了一个双向链表，头节点和尾节点都有记录，直接从尾节点插入一个元素即可，并不需要循环遍历，因此为o(1)的时间复杂度；

// 在链表的index(0-based)位置添加新的元素e
public void add(int index, e e){

if(index < 0 || index > size)
throw new illegalargumentexception(“add failed. illegal index.”);

node prev = dummyhead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;

prev.next = new node(e, prev.next);
size ++;
}

// 在链表头添加新的元素e
public void addfirst(e e){
add(0, e);
}

// 在链表末尾添加新的元素e
public void addlast(e e){
add(size, e);
}

3、获取链表中的元素

get(int index)表示获取index索引处的元素，跟添加元素类似，也是通过一个for循环找到index位置的节点，然后返回节点中的元素即可；时间复杂度为o(n);

getfirst()表示获取链表头元素，同理也是o(1)时间复杂度；

getlast()表示获取链表尾元素，同理也是o(n)时间复杂度；

// 获得链表的第index(0-based)个位置的元素
// 在链表中不是一个常用的操作
public e get(int index){

if(index < 0 || index >= size)
throw new illegalargumentexception(“get failed. illegal index.”);

node cur = dummyhead.next;
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
return cur.e;
}

// 获得链表的第一个元素
public e getfirst(){
return get(0);
}

// 获得链表的最后一个元素
public e getlast(){
return get(size - 1);
}

4、修改和查找元素

set(int index, e e)表示修改index索引处的元素为e；同理也是通过一个for循环找到index索引对应的node节点，然后修改元素值即可；

contains(e e)返回链表是否存在元素e，通过一个while循环在链表中遍历节点，找到返回true，遍历完仍没找到返回false；

// 修改链表的第index(0-based)个位置的元素为e
// 在链表中不是一个常用的操作
public void set(int index, e e){
if(index < 0 || index >= size)
throw new illegalargumentexception(“set failed. illegal index.”);

node cur = dummyhead.next;
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
cur.e = e;
}

// 查找链表中是否有元素e
public boolean contains(e e){
node cur = dummyhead.next;
while(cur != null){
if(cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}

5、从链表中删除元素

remove(int index)表示删除index索引处的节点，首先通过一个for循环找到待删除节点，然后将待删除节点的前一个节点的后一个节点指向待删除节点的后一个节点，这样即可删除节点；最后将删除节点的下一个节点指向null，便于垃圾回收；

removefirst()表示删除链表头节点，时间复杂度为o(1);

removelast()表示删除链表尾节点，时间复杂度为o(n);

removeelement(e e)表示删除元素e对应的节点，跟查找结点一样，首先通过while循环找到此节点，然后跟remove函数一样操作即可删除节点；

// 从链表中删除index(0-based)位置的元素, 返回删除的元素
// 在链表中不是一个常用的操作
public e remove(int index){
if(index < 0 || index >= size)
throw new illegalargumentexception(“remove failed. index is illegal.”);

node prev = dummyhead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;

node deletenode = prev.next;
prev.next = deletenode.next;
deletenode.next = null;
size --;

return deletenode.e;
}

// 从链表中删除第一个元素, 返回删除的元素
public e removefirst(){
return remove(0);
}

// 从链表中删除最后一个元素, 返回删除的元素
public e removelast(){
return remove(size - 1);
}

// 从链表中删除元素e
public void removeelement(e e){

node prev = dummyhead;
while(prev.next != null){
if(prev.next.e.equals(e))
break;
prev = prev.next;
}

if(prev.next != null){
node delnode = prev.next;
prev.next = delnode.next;
delnode.next = null;
size --;
}
}