【数据结构】模拟实现LinkedList

刺骨的言语ヽ痛彻心扉 2024-02-21 03:31 71阅读 0赞

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;//双向链表的尾节点
    }

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()

实现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成为新的头节点
    	}
    }

实现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成为尾节点
    	}
    }

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

public int size(){
        
    	ListNode cur = head;
    	int count = 0;
    	while (cur!=null){
        
    		count++;
    		cur = cur.next;
    	}
    	return count;
    }

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

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

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

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

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