链表各个操作中,数据的删除比较特殊,其中具体操作如图所示:
链表删除操作
java实现动态链表代码:
public class LinkedList<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
@SuppressWarnings("unused")
public Node(E e){
this(e, null);
}
public Node(){
this(null, null);
}
@Override
public String toString(){
return e.toString();
}
}
private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node();
size = 0;
}
// 获取链表中的元素个数
public int getSize(){
return size;
}
// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}
// 在链表的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);
}
// 获得链表的第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);
}
// 查找链表中是否有元素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;
}
// 从链表中删除index(0-based)位置的元素, 返回删除的元素
// 在链表中不是一个常用的操作,练习用:)
public E remove(int index){
if(index<0 || index >size){
throw new IllegalArgumentException("remove failed. Illegal index.");
}
Node prev = dummyHead;
for(int i=0;i<index;i++){
prev = prev.next;
}
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.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 --;
}
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
res.append(cur + "->");
res.append("NULL");
return res.toString();
}
}
具体的测试代码:
public static void main(String args[]){
LinkedList<Integer> arrayList = new LinkedList<Integer>();
for(int i =0;i<10;i++){
arrayList.add(i, i);
}
System.out.println(arrayList.toString());
System.out.println(arrayList.contains(5));
System.out.println(arrayList.get(8));
arrayList.removeElement(3);
System.out.println(arrayList.toString());
System.out.println(arrayList.remove(5));
System.out.println(arrayList.toString());
}
测试结果:
测试结果
链表的时间复杂度分析:
添加操作 删除操作 添加操作 总结
网友评论