Java,  算法和数据结构

如何实现链表这种数据结构

零 特征说明

我们前面实现的动态数组、栈、队列,虽然说是动态数据结构,其实,其底层是依赖一个resize()方法来实现的。

而,链表其本质上是一个真正的动态数据结构。如同火车头挂接一节一节的车厢一样。

另外,跟数组比较起来,数组要求在内存中分配的内存空间必须是连续的,而链表则不需要连续的内存空间。正式由于这个原因,对于数组查找第n个元素可以直接使用下标来寻找,而链表则不能支持根据索引下标来随机访问。

一 实现思路

链表通过一个”结点”的数据结构来实现,每个结点中存放具体元素+指向下一个结点的指针。当某个结点的下一个指针为NULL时,则该结点是最后1个元素,也就意味着链表到此结束了。

另外,在链表中开辟一个头指针,它是结点这种数据类型的,用于指向链表中的第1个元素。

开辟一个整型变量size,用于记录链表中当前有多少个元素。

二代码实现

1 实现LinkedList类及其内部类Node
public class LinkedList<E>{
  
  //实现链表的结点元素的内部类
  private class Node{
    //结点中存放的元素
    public E e;
    //指向下一个结点的指针
    public Node next;
    
    //constructor
    public Node(E e,Node next){
      this.e=e;
      this.next=next;
    }
    public Node(E e){
      this(e,null);
    }
    public Node(){
      this(null,null);
    }
    
    @Override
    public String toString(){
      return e.toString();
    }
  }
  //指向链表中的第一个元素
  private Node head;
  
  //记录链表中有多少个元素
  private int size;
  
  //constructor
  public LinkedList(){
    //链表中第1个元素为空
    head=null;
    size=0;
  }
  
  //查看链表元素个数
  public int getSize(){
    return size;
  }
  
  //链表是否为空
  public boolean isEmpty(){
    return size == 0;
  }
}

这样,我们动手实现了1个链表的基本框架:内部类Node用于表示每个结点,包含元素值和指向下一个结点的指针;链表中指向第1个结点的指针;记录链表中元素(结点)的个数的成员变量size;

2 实现向链表中插入元素的方法
//链表头部添加元素
    public void addFirst(E e) {
        Node node = new Node(e);
        //先将新结点的下一个元素指向head.next,即链表头结点,这样就相当于在头部添加元素
        node.next = head;
        //然后,让head指向这个结点,进而这个新加的元素就成了第1个元素
        head = node;
        size++;
    }

//在第i个位置处插入元素
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed.Illegal index");
        }
        if (index == 0) {
            addFirst(e);
            return;
        }
        Node node = new Node(e);
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    //在最后位置处添加元素
    public void addLast(E e) {
        add(size,e);
    }
3 带头结点的链表插入

前面,我们实现的链表,由于在链表任意位置插入元素时,需要特殊判断,插入位置是否在链表头,略微麻烦。于是,我们想到给链表设置一个虚拟头结点,让其指向链表的第1个结点。

public class LinkedList<E> {
    private class Node{
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
    //此处构建1个虚拟头结点
    private Node dummyHead;
    private int size;

    public LinkedList() {
     //构造链表时,虚拟头结点的元素为空,指向的下一个结点(链表中真正的第1个结点)也为空
        dummyHead =new Node(null,null);
        size = 0;
    }

    //查看链表中有多少元素
    public int getSize() {
        return size;
    }

    //链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //链表头部添加元素
    public void addFirst(E e) {
        add(0, e);
    }

    //在第i个位置处插入元素
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed.Illegal index");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    //在最后位置处添加元素
    public void addLast(E e) {
        add(size,e);
    }
}
4 获取第index位置处的元素
//查找链表第index位置处元素,练习用
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed.Illegal index");
        }
        Node curr = dummyHead.next;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.e;
    }
//查找第1个元素
    public E getFirst() {
        return get(0);
    }
​
    //查找最后1个元素
    public E getLast() {
        return get(size - 1);
    }
5 修改第index位置处元素为e
//修改第index位置处元素为e
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed.Illegal index");
        }
        Node curr = dummyHead.next;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        curr.e = e;
    }
6 判断是否存在元素e
//判断是否存在元素e
    public boolean contains(E e) {
        Node curr = dummyHead.next;
        //两种实现方式,for loop和while loop
//        for (int i = 0; i < size; i++) {
//            if (curr.e.equals(e)) {
//                return true;
//            }
//            curr = curr.next;
//        }
        while (curr != null) {
            if (curr.e.equals(e)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }
7 复写Object类的toString()
  @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("LinkedList:size %d\n", size));
        Node curr = dummyHead.next;
        for (int i = 0; i < size; i++) {
            stringBuilder.append(curr);
            curr = curr.next;
            if (i != size - 1) {
                stringBuilder.append("->");
            }
        }
        return stringBuilder.toString();
    }
8 删除第index位置处元素并返回
//删除第index位置处元素
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Delete failed.Illegal index");
        }
        Node pre = dummyHead;
        //pre是待删除元素的前1个
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        //retNode存放但删除元素并返回
        Node retNode = pre.next;
        //pre的下一个元素指向待删除元素的next,从而删除了retNode这个待删除元素
        pre.next = retNode.next;
        //retNode.next=null,相当于retNode和我们的链表解除了关系
        size--;
        return retNode.e;
    }
​
    //删除第1个元素并返回
    public E removeFirst() {
        return remove(0);
    }
​
    //删除最后1个元素并返回
    public E removeLast() {
        return remove(size - 1);
    }
9 测试所有方法
public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            linkedList.add(i,i);
        }
        System.out.println(linkedList);
        System.out.println("contains(8):?"+linkedList.contains(8));
        linkedList.set(5, 55);
        System.out.println("remove(3): "+linkedList.remove(3));
        System.out.println("after set(5,55):");
        System.out.println(linkedList);
​
        System.out.println("get(1): "+linkedList.get(1));
        System.out.println("getFirst(): "+linkedList.getFirst());
        System.out.println("getLast(): "+linkedList.getLast());
        System.out.println("removeFirst():"+linkedList.removeFirst());
        System.out.println("removeLast():"+linkedList.removeLast());
        System.out.println(linkedList);
    }
//结果
LinkedList:size 10
0->1->2->3->4->5->6->7->8->9
contains(8):?true
remove(3): 3
after set(5,55):
LinkedList:size 9
0->1->2->4->55->6->7->8->9
get(1): 1
getFirst(): 0
getLast(): 9
removeFirst():0
removeLast():9
LinkedList:size 7
1->2->4->55->6->7->8
10 复杂度分析

添加:addLast(E e) O(n);add(int index,E e) O(n); addFirst(E e) O(1);

删除:removeLast() O(n); remove(int index) O(n); removeFirst() O(1);

修改:set(int index,E e) O(n);

查找:contains(E e) O(n); getFirst() O(1);get(int index) O(n);getLast() O(n);

因此,我们可以得出实现的这种链表,其增删改查的时间复杂度都是O(n)。可是,我们为什么还要使用链表这种数据结构呢,它有什么用处呢?当我们指在链表头执行增删改查时,其时间复杂度瞬间降低到O(1)。结合栈这种数据结构,栈的操作都在栈顶位置,当我们用链表头来充当栈顶位置时,所有对于栈的操作:入栈、出栈、查看栈顶元素,我们就可以直接使用链表的链表头添加元素addFirst()/删除元素removeFirst()/getFirst()了,且时间复杂度都是O(1)。

三 小结

关于链表的实现,有2个比较麻烦的地方,就是头指针和引入虚拟头结点。引入虚拟头结点的目的主要是为了实现在链表头插入新结点/删除头结点的操作方便。引入的虚拟头结点都是指向链表中第一个真正的结点,这样链表中的所有结点都有了1个前驱结点。

一旦接受并理解了虚拟头结点,实现和使用链表就比较轻松一些了。引入虚拟头结点之后,所有对于链表的增、删、改、查,就都相当于对数组的操作了,结点下标从0开始,所有对于第index个位置处的增删改查,代码中的索引上限都是index,跟遍历数组是一样的思路。只不过呢,对于链表的增加和删除操作中,临时变量Node pre都是直接指向dummyHead,我们引入虚拟头结点的目的就是为了便于对链表头的插入和删除嘛。查找或修改第index个位置处的元素,我们都是把临时变量Node curr指向dummyHead.next。

留言