0%

手写简易LinkedList

发表于 更新于 分类于

​ LinkedList属于List接口的实现类之一，与ArrayList不同之处是采用的存储结构不同，ArrayList的数据结构为线性表，而LinkedList数据结构是链表。链表数据结构的特点是每个元素分配的空间不必连续、插入和删除元素时速度非常快、但访问元素的速度较慢。LinkedList是一个双向链表, 当数据量很大或者操作很频繁的情况下，添加和删除元素时具有比ArrayList更好的性能。但在元素的查询和修改方面要弱于ArrayList。LinkedList类每个结点用内部类Node表示，LinkedList通过first和last引用分别指向链表的第一个和最后一个元素，当链表为空时，first和last都为NULL值。

一，关于链表

类型 包含节点 第一和最后节点指向
单向链表 尾节点 尾的next=>null
单向循环链表 尾节点 尾的next=>头
双向链表 头，尾节点 每个节点头尾各自对应前后元素，first和last的prev/next对应null
双向循环链表 头，尾节点 last的next=>first，first的next=>last

二，关于LinkedList

LinkedList 是一个继承于AbstractSequentialList的双向循环链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。

三，实现的功能

​ –尾部添加，索引查找，索引插入，索引修改，索引删除

四，构建节点

1
class Node<E>{		//作为LinkedListC的内部类
2
    Node<E> prev;	//头节点
3
    E data;			//数据
4
    Node<E> next;	//尾节点
5
    public Node(E e){
6
        this.data=e;
7
    }
8
    public Node(Node<E> prev, E data, Node<E> next) {
9
        this.prev = prev;
10
        this.data = data;
11
        this.next = next;
12
    }
13
}

五，构建LinkedList

1
public class LinkedListC<E> {
2
    private int size=0;		//链表长度
3
    private Node<E> first;	//首部
4
    private Node<E> last;	//尾部
5
    
6
    @Override				//重写toString方法，便于观察
7
    public String toString() {
8
        StringBuilder llc=new StringBuilder("[");
9
        for(int i=0;i<size;i++){
10
            llc.append(first.data+",");
11
            first=first.next;
12
        }
13
        if(size!=0){
14
            llc.setCharAt(llc.length()-1,']');
15
        }else {
16
            llc.append("]");
17
        }
18
        return llc.toString();
19
    }
20
}

六，方法的编写

获取索引所代表的节点[getNode(int index)]

1
public Node getNode(int index){			//分成了前后两部分，提高效率
2
        if(index<0||index>=size){
3
            throw new RuntimeException("索引越界："+index);
4
        }
5
        if(index<=size/2){				//前半部分节点
6
            Node node=first;
7
            for(int i=0;i<index;i++){
8
                node=node.next;
9
            }
10
            return node;
11
        }else {							//后半部分节点
12
            Node node=last;
13
            for(int i=0;i<size-index-1;i++){
14
                node=node.prev;
15
            }
16
            return node;
17
        }
18
    }

尾部添加[add(E,e)]

1
public void add(E e){
2
        Node<E> node=new Node<E>(e);	//新建节点
3
        if(first==null){				//第一次添加，设置头尾
4
            first=node;
5
            last=node;
6
        }else{							//其他添加，尾部插入新节点
7
            							//并改变first的prev指向和last
8
            last.next=node;
9
            node.prev=last;
10
            node.next=first;
11
            last=node;
12
            first.prev=last;
13
        }
14
        size++;							//长度+1
15
    }

索引添加[insert(int index,E e)]

1
public void insert(int index,E e){
2
        Node node=getNode(index);		//获取索引的节点
3
        Node newnode=new Node(e);
4
        if(node.next!=null) {			
5
            Node node_prev = node.prev;
6
            newnode.next = node;
7
            newnode.prev = node_prev;
8
            node_prev.next = newnode;
9
            node.prev = newnode;
10
        }else {							//只有一个节点的情况
11
            newnode.prev=node;
12
            node.next=newnode;
13
        }
14
        size++;
15
        if(index==0){					//如果是第一个节点，将其设为first
16
            first=newnode;
17
        }
18
    }

索引查询[get(int index)]

1
public String get(int index){
2
        return getNode(index).data.toString();
3
    }

索引修改[set(int index)]

1
public void set(int index,E e){
2
        System.out.println("即将将索引为"+index+"的数改为"+e);
3
        getNode(index).data=e;
4
    }

索引删除[remove(int index)]

1
public void remove(int index){
2
        Node node=getNode(index);
3
        System.out.println("要删除的索引是："+index);
4
        if(node.next!=null){				//不止一个时
5
            Node node_prev=node.prev;
6
            Node node_next=node.next;
7
            node_prev.next=node_next;
8
            node_next.prev=node_prev;
9
            if(index==0){					//第一个时，设置为first
10
                first=node_next;
11
            }
12
        }else {								//只有一个时，恢复出厂设置
13
            first=null;
14
            last=null;
15
        }
16
        size--;								//长度-1
17
    }

七，测试过程

1
public static void main(String[] args) {
2
        LinkedListC<Integer> li= new LinkedListC<>();
3
        System.out.println(li.toString());//检验toString方法，此时为空链表
4
        li.add(1);				//添加一个1
5
        System.out.println("执行add方法后："+li.toString());
6
        li.set(0,9);			//将刚刚的1修改为9
7
        System.out.println("执行set方法后："+li.toString());
8
        System.out.println("执行get方法后："+li.get(0));	//获取第一个
9
        li.remove(0);			//移除那个1
10
        System.out.println("执行remove方法后："+li.toString());
11
        li.insert(0,5);		//在那个1的地方插入5(由于已经被移除，所以不存在0索引将抛出异常)
12
        System.out.println("执行insert方法后："+li.toString());
13
    }

运行结果：

八，总结

头发-1