单链表的基本操作

单链表基本操作

1. 创建

public class MySingleList {

    public MySingleList() {
        this.head = null;
    }

    class Node{
        private int data;
        public Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }

        public int getData() {
            return data;
        }

        public Node getNext() {
            return next;
        }

    }

    public Node getHead() {
        return head;
    }

    private Node head;
    int size;
  }

2. 头插

public void addFirst(int data) {
        Node node = new Node(data);
        //第一次插入数据
        if(this.head==null){
            this.head = node;
        }else {
            node.next = head;
            head = node;
        }
        size++;
    }

3. 尾插

public void addLast(int data) {
        Node node = new Node(data);
        Node cur = head;
        //如果第一次插
        if(cur == null){
            this.head = node;
        }else {
            while (cur.next!=null){
                cur = cur.next;
            }
            cur.next = node;
        }
        size++;
    }

4. 任意位置插入

    public Node searchIndex(int index){
        checkIndex(index);
       Node cur = this.head;
       for(int i = 0;i<index;i++){
           cur = cur.next;
       }
       return cur;
    }
    public void checkIndex(int index){
        if(index<0 || index >=getLength())
            throw new UnsupportedOperationException("下标不合法");
    }

    public void  addIndex(int index, int data) {
        checkIndex(index);
        Node newNode = new Node(data);
        if(index==0){
            addFirst(data);
        }
        Node prevNode = searchIndex(index-1);
        Node nextNode = prevNode.next;
        prevNode.next = newNode;
        newNode.next = nextNode;
         size++;

    }

   

5. 链表中是否有key值

public boolean contains(int key) {
        Node cur = this.head;
        for(int i = 0;i<size;i++){
            if(cur.data == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
  }

6. 删除第一次出现为key的值

private Node searchPre(int key){
        //1.是不是第一个节点  if(head.data == key)
        Node pre = this.head;
        if(pre.data == key){
            return this.head;
        }
        while (pre.next!=null){
            if(pre.next.data==key){
                return pre;
            }
            pre = pre.next;
        }
        return null;

    }
    @Override
    public int remove(int key) {
        Node pre = searchPre(key);
        int oldData = 0;
        if(pre == null){
            throw new UnsupportedOperationException("没有找到");
        }
        if(pre == this.head && pre.data == key){
            oldData = pre.data;
            this.head = pre.next;
            size--;
            return oldData;
        }
        Node delNode = pre.next;
        pre.next = delNode.next;
        size--;
        return delNode.data;


    }

7. 得到链表长度

public int getLength() {
       return size;
    }


  

8. 打印链表

  
    public void display() {
       Node cur = this.head;

       while (cur!=null){
           System.out.print(cur.data+" ");
           cur = cur.next;
       }
        System.out.println();
    }

9. 销毁链表

 public void clear() {
        while (this.head!=null){
            Node cur = this.head.next;
            this.head.next = null;
            this.head = cur;
        }
    }

10. 一个有序链表，删除重复节点

    public Node deleteDuplication(){
        Node node = new Node(-1);  //虚拟节点
        Node tmpHead = node;
        Node cur = this.head;
        while (cur!=null){
            if(cur.next!=null && cur.data == cur.next.data){
                while (cur.next!=null && cur.data == cur.next.data){
                    cur = cur.next;
                }
                cur = cur.next;
                tmpHead.next = cur;

            }else {
                //确定不为重复的节点
                tmpHead.next = cur;
                tmpHead = cur;
                cur = cur.next;
            }
        }
        return node.next;
    }