【数据结构】模拟实现LinkedList

LinkedList是双向链表结构可以适用于任意插入场景下的插入和删除，效率较高，时间复杂度为O(1)。

模拟实现

public class MyLinkedList {

    static class ListNode{
        private int val;//值域
        private ListNode prev;//前驱
        private ListNode next;//后继

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//双向链表的头节点
    public ListNode last;//双向链表的尾节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LinkedList常用方法

//头插法
public void addFirst(int data)
    
//尾插法
public void addLast(int data)
    
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data)
    
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key)
    
//删除第一次出现关键字为key的节点
public void remove(int key)
    
//删除所有值为key的节点
public void removeAllKey(int key)
    
//得到链表的长度
public int size()
    
//清空链表
public void clear()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

实现addFirst方法（头插法）

public void addFirst(int data){
	ListNode node = new ListNode(data);
    //如果链表为空 插入的元素就是头节点和尾节点
	if (head==null){
		head = node;
		last = node;
	}else {
		node.next = head;//使node的后继是现在的头节点
		head.prev = node;//使现在的头节点的前驱是node
		head = node;//让node成为新的头节点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

实现addList方法（尾插法）

public void addLast(int data){
	ListNode node = new ListNode(data);
    //和头插一样
	if (last==null){
		head = node;
		last = node;
	}else {
		last.next = node;//使现在尾节点的后继为node
		node.prev = last;//使node的前驱为现在的尾节点
		last = last.next;//让node成为尾节点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

实现size方法（求链表长度）

public int size(){
	ListNode cur = head;
	int count = 0;
	while (cur!=null){
		count++;
		cur = cur.next;
	}
	return count;
}
1
2
3
4
5
6
7
8
9

实现addIndex方法（在任意位置插入元素）

public void addIndex(int index,int data){
    //插入的位置如果为0 可以使用头插法
	if (index==0){
		addFirst(data);
		return;
	}
    //如果在最后一个位置插入 可以使用尾插法
	if (index==size()){
		addLast(data);
		return;
	}
    
	ListNode node = new ListNode(data);
    //判断要插入的下标是否合法
	if (index<0||index>size()){
		System.out.println("index 不合法"+index);
		return;
	}
	ListNode cur = head;
    //让cur走到要插入的位置
	while (index!=0){
		cur = cur.next;
		index--;
	}
	node.next = cur;
	cur.prev.next = node;
	node.prev = cur.prev;
	cur.prev = node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

实现contains方法（查找是否包含关键字key是否在单链表当中）

public boolean contains(int key){
	if (head==null){
		return false;
	}
	ListNode cur = head;
	while (cur!=null){
		if (cur.val==key){
			return true;
		}
		cur = cur.next;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

实现remove方法（删除第一次出现关键字为key的节点）

public void remove(int key){
    ListNode cur = head;
    while (cur!=null){
        if (cur.val==key){
            //删除头节点
            if (cur==head){
                head = head.next;
                if (head==null){
                    //只有一个头节点
                    cur.prev=null;

                }else {
                    last=null;
                }
                }else {
                    if (cur.next!=null){
                        //删除中间节点
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }else {
                    //删除尾节点
                    cur.prev.next=cur.next;
                    last=last.prev;
                }
            }
            return;
        }else {
            cur=cur.next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

实现removeAllkey（删除所有值为key的节点）

public void removeAllKey(int key){
    ListNode cur = head;
    while (cur!=null){
        if (cur.val==key){
            //删除头节点
            if (cur==head){
                head = head.next;
                if (head==null){
                    //只有一个头节点
                    cur.prev=null;
                }else {
                    last=null;
                }
                }else {
                    if (cur.next!=null){
                        //删除中间节点
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                	}else {
                    	//删除尾节点
                    	cur.prev.next=cur.next;
                    	last=last.prev;
                }
            }
            cur=cur.next;
        }else {
            cur=cur.next;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

实现clear方法（清除链表）

public void clear(){
    ListNode cur = head;
    while (cur!=null){
        ListNode curNew = cur.next;
        cur.prev=null;
        cur.next=null;
        cur = curNew;
    }
    head=null;
    last=null;
}
1
2
3
4
5
6
7
8
9
10
11