第三章 线性结构+链式存储= ?以及单链表的定义与实现

第三章 线性结构+链式存储= ?以及单链表的定义与实现

目录

主要内容一、动态链表

1、定义2、相关名词3、注意点（java中没有指针概念）（理解内存分配）

我们来画个图（配合相应代码）理解一下

1）、链表初始化2）、添加元素3）、再添加一个元素 二、单向链表linkedSinglyList

1、添加元素

1）、当链表为空时，添加元素2）、添加到首元素时3）、添加到尾元素时4）、按索引添加到中间位置时5）、添加元素代码实现 2、删除元素

1）、删除头结点2）、删除尾结点3）、删除中间元素4）、当链表中只剩一个元素时，删除5）、删除元素代码实现 3、单链表整体代码

主要内容

单向链表
单向循环链表
双向循环链表
链栈
链队列

一、动态链表 1、定义

为了表示每个数据元素ai与其直接后继数据元素ai+1 之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。
n个结点(ai的存储映像)链结成一个链表，即为线性表(a1, a2, …, an)的链.式存储结构，因为此链表的每个结点中只包含-一个指针域，所以叫做单链表。

2、相关名词

头结点是指链表中的第一个结点，有真实头结点和虚拟头结点之分
真实头结点：其第一个结点用于存储数据（常用）

虚拟头结点：其第一个结点不许存储数据

头指针：仅仅是一个引用变量，存储头结点地址的指针而已
尾指针：同头指针，不过是链表中最后一个结点的指针而已

数据结构是灵活的，没有一定的存在，也没有一定的不存在。根据需求比如可以不要尾指针，也可以定义一个中间指针、总结点数量、最值等等，因为代码是自己写的，根据自己需求添加需要的，删除不需要的。

3、注意点（java中没有指针概念）（理解内存分配）

java中是没有指针存在的，我们在java中所提到的指针只是我们逻辑上的理解，那我们是怎么实现链式存储的呢？

这里要是不细想的话，可以不用考虑

我们再次采用了内部类的方法

//概括性的举个例子，代码并不完整
public class linkedSinglyList {
    //定义结点对象，内部类
    private class Node {
        E data;     //数据域
        Node next;  //指针域
        public Node() {//内部类构造函数
            this.data = 1;
            this.next = null;
        }
        ...
    }
    public void add(int index, E element) {//添加元素方法
        Node n = new Node(element);
        head = n;
        tail = n;
    }
    private Node head;  //头指针，并没有开辟内存
    private Node tail;  //尾指针;
    
    public linkedSinglyList() {//链表构造函数
        head = null;
        tail = null;
        size = 0;
    }
    ...
    
}

我们来画个图（配合相应代码）理解一下 1）、链表初始化

//初始化构造方法
    public linkedSinglyList() {//链表构造方法
        head = null;
        tail = null;
        size = 0;
    }

2）、添加元素

//调用add方法
public void add(int index, E element) {//添加元素方法
    Node n = new Node(element);
    head = n;
    tail = n;
}
//方法里开辟了新的内存，所以先执行内部类构造函数
public Node() {
    this.data = 1;
    this.next = null;
}
//然后进行head和tail的赋值

这里内部类的初始化的null和链表一开始初始化的null一样的理解

3）、再添加一个元素

tail.next = n;//上一步，tail是和head指向同一片空间，这一步，就是让前一个的地址域赋值新开辟的这块地址
tail = n;//再让tail指向新开辟的这块地址

二、单向链表linkedSinglyList

linkedSinglyList就是线性结构链式存储方式的具体实现，称为单链表

主要的还是”增删改查“功能。先分段讲解一下

1、添加元素 1）、当链表为空时，添加元素

2）、添加到首元素时

3）、添加到尾元素时

4）、按索引添加到中间位置时

需要定义一个指针，从头遍历，找到需要删除的元素

5）、添加元素代码实现

//实现代码
public void add(int index, E element) {
    if (index < 0 || index > size) {//index是索引，索引超过范围，将会抛出异常
        throw new IllegalArgumentException("add index out of range");
    }
    Node n = new Node(element);
    if (size == 0) {//当链表没有元素的时候
        head = n;
        tail = n;
    } else if (index == 0) {//当添加到头结点的时候
        n.next = head;
        head = n;
    } else if (index == size) {//当添加到尾节点的时候
        tail.next = n;
        tail = n;
    } else {//添加到链表的中间位置，需要根据索引从头遍历
        Node p = head;
        for (int i = 0; i < index - 1; i++) {
            p = p.next;
        }
        n.next = p.next;
        p.next = n;
    }
    size++;
}

2、删除元素 1）、删除头结点

定义一个指针先指向头结点，然后头结点后移，删除原来的结点

2）、删除尾结点

3）、删除中间元素

直接遍历到需要删除的元素前一个位置，然后让前一个元素的指针指向下一个即可

4）、当链表中只剩一个元素时，删除

直接让head和tail赋值为空即可

5）、删除元素代码实现

public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove index out of range");
        }
        E ret = null;
        if (size == 1) {
            ret = head.data;
            head = null;
            tail = null;
        } else if (index == 0) {
            Node n = head;
            ret = n.data;
            head = n.next;
            n.next = null;
        } else if (index == size - 1) {
            Node p = head;
            while (p.next != tail) {
                p = p.next;
            }
            ret = tail.data;
            p.next = null;
            tail = p;
        } else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            Node n = p.next;
            ret = n.data;
            p.next = n.next;
            n.next = null;
        }
        size--;
        return ret;
    }

查找和修改基本上就没什么了

3、单链表整体代码

package p3.链式结构;

import p1.接口.List;
import p2.线性结构.ArrayList;

import java.util.Comparator;
import java.util.Iterator;
//单向链表
public class linkedSinglyList implements List {

    //定义结点对象
    private class Node {
        E data;     //数据域
        Node next;  //指针域
        public Node(){
            this(null,null);
        }
        public Node(E data) {
            this(data,null);
        }
        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
        @Override
        public String toString() {
            return data.toString();
        }
    }
    private Node head;  //头指针
    private Node tail;  //尾指针
    private int size;   //元素的个数

    public linkedSinglyList() {
        head = null;
        tail = null;
        size = 0;
    }

    public linkedSinglyList(E[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr is null");
        }
        for (int i = 0; i < arr.length; i++) {
            add(arr[i]);
        }
    }

    @Override
    public void add(E element) {
        add(size, element);
    }

    @Override
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index out of range");
        }
        Node n = new Node(element);
        if (size == 0) {
            head = n;
            tail = n;
        } else if (index == 0) {
            n.next = head;
            head = n;
        } else if (index == size) {
            tail.next = n;
            tail = n;
        } else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            n.next = p.next;
            p.next = n;
        }
        size++;
    }

    @Override
    public void remove(E element) {
        int index = indexOf(element);
        if (index != -1) {
            remove(index);
        }
    }
    @Override
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove index out of range");
        }
        E ret = null;
        if (size == 1) {
            ret = head.data;
            head = null;
            tail = null;
        } else if (index == 0) {
            Node n = head;
            ret = n.data;
            head = n.next;
            n.next = null;
        } else if (index == size - 1) {
            Node p = head;
            while (p.next != tail) {
                p = p.next;
            }
            ret = tail.data;
            p.next = null;
            tail = p;
        } else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            Node n = p.next;
            ret = n.data;
            p.next = n.next;
            n.next = null;
        }
        size--;
        return ret;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get index out of range");
        }
        if (index == 0) {
            return head.data;
        } else if (index == size - 1) {
            return tail.data;
        } else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            return p.data;
        }
    }

    @Override
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get index out of range");
        }
        E ret = null;
        if (index == 0) {
            ret = head.data;
            head.data = element;
        } else if (index == size - 1) {
            ret = tail.data;
            tail.data = element;
        } else {
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;
            }
            ret = p.data;
            p.data = element;
        }
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int indexOf(E element) {
        Node p = head;
        int index = 0;
        while (!p.data.equals(element)) {
            p = p.next;
            index++;
            if (p == null) {
                return -1;
            }
        }
        return index;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    @Override
    public boolean isEmpty() {
        return size == 0 && head == null && tail == null;
    }

    @Override
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void sort(Comparator c) {
        if (c == null) {
            throw new IllegalArgumentException("comparator can not be null");
        }
        //此处的插入排序O(n^3)
        
        if (size == 0 || size == 1) {
            return;
        }
        Node nodeA = head;
        Node nodeB = nodeA.next;
        while (true) {
            while (true) {
                if (c.compare(nodeA.data, nodeB.data) > 0) {
                    swap(nodeA, nodeB);
                }
                if (nodeB == tail) {
                    break;
                }
                nodeB = nodeB.next;
            }
            if (nodeA.next == tail) {
                break;
            }
            nodeA = nodeA.next;
            nodeB = nodeA.next;
        }
    }

    private void swap(Node nodeA, Node nodeB) {
        E temp = nodeA.data;
        nodeA.data = nodeB.data;
        nodeB.data = temp;
    }

    @Override
    public List subList(int fromIndex, int toIndex) {
        //0 <= fromIndex <= toIndex <= size - 1    [fromIndex,toIndex]
        if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
            throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");
        }

        linkedSinglyList list = new linkedSinglyList<>();
        
        Node nodeA = head;
        for (int i = 0; i < fromIndex; i++) {
            nodeA = nodeA.next;
        }
        Node nodeB = head;
        for (int i = 0; i < toIndex; i++) {
            nodeB = nodeB.next;
        }
        Node p = nodeA;
        while (true) {
            list.add(p.data);
            if (p == nodeB) {
                break;
            }
            p = p.next;
        }
        return list;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()) {
            sb.append(']');
        } else {
            Node p = head;
            while (true) {
                sb.append(p.data);
                if (p == tail) {
                    sb.append(']');
                    break;
                }
                sb.append(',');
                sb.append(' ');
                p = p.next;
            }
        }
        return sb.toString();
    }

    @Override
    public Iterator iterator() {
        return new linkedSinglyListIterator();
    }

    class linkedSinglyListIterator implements Iterator {
        private Node cur = head;

        @Override
        public boolean hasNext() {
            return cur != null;
        }
        @Override
        public E next() {
            E ret = cur.data;
            cur = cur.next;
            return ret;
        }
    }
}