每日一博|02 单链表的基本 *** 作

单链表的基本 *** 作

链表是一种物理存储结构上非连续，但是逻辑顺序连续的存储结构。链表结构丰富，主要包含8种链表结构，分别为：带头结点的单链表、不带头结点的单链表、带头结点的双链表、不带头结点的双链表、带头结点的循环链表、不带头结点的循环链表、带头结点的非循环链表以及不带头结点的非循环链表。本文主要针对Java数据结构中常用到的带头结点的单链表的基本 *** 作进行实践。

1 构建单链表信息

通过泛型构建单链表类：

public class SingleLinklist<E> {
    public static class Node<E> {
        E value;  //结点的值
        Node<E> next;  //结点的下一个指向

        public Node(E value) {
            this.value = value;
        }
    }
        Node<E> head;  //定义头结点
}

2 打印链表的每个元素

通过链表的遍历来打印每个元素的值

public String toString(){
        Node<E> cur = head;
        String str = "[";
        while(null != cur){
            str += cur.value;
            if(null != cur.next){
                str += ",";
            }
            cur = cur.next;
        }
        str += "]";
        return str;
    }

3 计算链表中元素的个数

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

4 找到链表的最后一个结点

链表最后一个结点的特点：该结点的next为null，因此可以根据这个条件进行遍历判断

public E printLastElement() {
        Node<E> cur = head;
        if (null == head) {
            return null;
        } else {
            while (null != cur.next) {
                cur = cur.next;
            }
            return cur.value;
        }
    }

5 找到链表的倒数第二个结点

a、如果链表只有一个结点或者没有结点，则不能找到链表的倒数第二个结点；

b、当 链表的结点数 >= 2时，通过遍历来寻找链表的倒数第二个结点；

public E printLastSecondElement(){
        Node<E> cur = head;
        Node<E> prev = null;
        if(null == head || null == head.next ){
            return null;
        }else{
            while(null != cur.next){
                prev = cur;
                cur = cur.next;
            }
            return prev.value;
        }
    }

6 找到链表的第 n 个结点（链表的长度 >= n)

public E printNElement(int n){
        Node<E> cur = head;
        if(0 == n){
            return null;
        }else{
            int count = n;
            while(0 != count){
                cur = cur.next;
                count--;
            }
            return cur.value;
        }
    }

7 找到链表中是否包含某个元素

public boolean contain(E e){
        Node<E> cur = head;
        if(null == head){
            return false;
        }else{
            while(null != cur){
                if(e.equals(cur)){
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    }

8 头插法

当链表为空时：

当链表不为空时：

public void addFirst(E data){
        Node<E> newNode = new Node(data);
        if(null == head){
           head = newNode;
        }else{
            newNode.next = head;
            head = newNode;
        }
    }

9 尾插法

public void addLast(E data){
        Node<E> newNode = new Node(data);
            Node<E> cur = head;
            while(null != cur.next){
                cur = cur.next;
            }
            cur.next = newNode;
    }

10 在指定位置处插入

在第一个结点前（即0号位置插入时），类似于头插法进行链表元素的插入

在其他位置处插入时：

public boolean addIndex(int position, E e){
        if(position < 0 || position > 1000){
            throw new IllegalArgumentException("addIndex:position非法");
        }else{
            Node<E> newNode = new Node(e);
            Node<E> cur = head;
            Node<E> prev = null;
            if(0 == position){
                addFirst(e);
                return true;
            }else{
                while(0 != position){
                    prev = cur;
                    cur = cur.next;
                    position--;
                }
                newNode.next = cur;
                prev.next = newNode;
                return true;
            }
        }
    }

11 删除第一次出现e的结点

public void remove(E e){
        Node<E> cur = head;
        Node<E> prev = null;
        if(null == head){
            return;
        }else{
            while(null != cur){
                if(e.equals(cur.value)){
                    cur.value = null;
                    if(prev == null){
                        head = cur.next;
                    }else {
                        prev.next = cur.next;
                    }
                    return;
                }
                prev = cur;
                cur = cur.next;
            }
        }
    }

12 删除e的所有结点

public void removeAllKey(E e){
        Node<E> cur = head;
        Node<E> prev = null;
        while(null != cur){
            if(e.equals(cur.value)){
                cur.value = null;
                if(null == prev){
                    head = cur.next;
                    cur = head;
                }else{
                    prev.next = cur.next;
                    cur = prev.next;
                }
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
    }