数据结构和算法-5.1-单链表&有序链表

定义

• 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的；
• 链表由多个链结点组成，每个链结点由两部分组成，一个存储数据元素的数据域，一个存储下一个结点地址的指针域；
• 在链表中，寻找一个特定元素的唯一方法，就是沿着这个元素的链一直向下寻找；

解决的问题

无序数组搜索慢，有序数组插入慢，且数组的删除效率低，大小固定；
链表则常用来替换数组，作为其他存储结构的基础，以解决上面问题；
除非需要频繁的用下标随机访问各个数据，否则很多地方都可以用链表代替数组。

分类：

• 单链表
• 双端链表
• 有序链表
• 双向链表
• 有迭代器的链表

单链表的实现（含迭代器）

1. 创建一个链结点类

public class Link<T> {
    public T data;//数据域
    public Link<T> next;//指针域, 指向下一个链结点
    //此处next为一个和自己类型相同的字段，因此也叫"自引用"式

    public Link(T data) {
        this.data = data;
    }

    public void display(){
        System.out.print("Link:{"+data.toString()+"}");
    }
}

2. 单链表实现类, 其中一些关键的地方都有注释，这里就不再多说了，

public class LinkList<T> {
    protected Link<T> first;//LinkList仅包含了一个数据项，即对第一个链结点的引用

    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 向链表插入数据
     *
     * @param value
     */
    public void insertFirst(T value) {
        //新建链结点，把数据传入这个链结点，将这个新的链结点的next字段指向原来的first的值，将first指向这个新的链结点
        Link<T> newLink = new Link<>(value);
        newLink.next = first;
        first = newLink;
    }

    public Link<T> deleteFirst() {
        Link temp = first;
        first = first.next;
        return temp;
    }

    public void display() {
        System.out.print("LinkList:{ ");
        Link current = first;
        while (current != null) {
            current.display();
            if (current.next != null)
                System.out.print(", ");
            current = current.next;
        }
        System.out.println("} ");
    }

    public Link<T> find(T value) {
        Link current = first;
        //找到才跳出循环，否则一直找，直到next==null，该链结点链表的最后一个
        while (!current.data.equals(value)) {
            if (current.next == null)
                return null;
            else
                current = current.next;
        }
        return current;
    }

    public Link<T> delete(T value) {
        Link current = first;//当前链结点
        Link previous = first;//当前值的前一个链结点
        if (current == null)
            return null;
        //找到才跳出循环，否则一直找，直到next==null，该链结点链表的最后一个
        while (!current.data.equals(value)) {
            if (current.next == null)
                return null;
            else {
                previous = current;
                current = current.next;
            }
        }
        if (current == first)
            //如果所找的值对应first链结点，就把first指向下一个链结点，也就是first.next
            first = first.next;
        else
            //如果不是对应first，就把该链结点的前一个链结点的指针next指向该链结点的下一个链结点，即current.next
            previous.next = current.next;
        return current;
    }

    public LinkIterator<T> iterator(){
        return new LinkIterator<>(this);
    }

    public Link<T> getFirst() {
        return first;
    }
}

上面的LinkIterator迭代器类的实现如下：

public class LinkIterator<T> {
    private LinkList<T> linkList;
    private Link<T> current;
    private Link<T> previous;

    public LinkIterator(LinkList<T> linkList) {
        this.linkList = linkList;
        reset();
    }

    private void reset() {
        current=linkList.getFirst();
        previous=null;
    }

    public Link<T> getCurrent() {
        return current;
    }

    public boolean hasNext(){
        return current!=null&&current.next!=null;
    }

    public Link<T> next(){
        previous=current;
        current=current.next;
        return previous;
    }

    public void remove(){
        if (current==linkList.first)
            linkList.first=linkList.first.next;
        else
            previous.next=current.next;
    }

}

3. 对单链表实现类的使用

  private static void testLinkList() {
        LinkList<String> linkList = new LinkList<>();
        for (int i = 0; i < 10; i++) {
            linkList.insertFirst("data_" + i);
            linkList.display();
        }
        linkList.find("data_3").display();
        linkList.delete("data_5").display();
        linkList.delete("data_7").display();
        linkList.delete("data_8").display();
        linkList.display();
   }

4. 迭代器的使用

  private static void testLinkIterator() {
        LinkList<String> linkList = new LinkList<>();
        for (int i = 0; i < 10; i++) {
            linkList.insertFirst("data_" + i);
            linkList.display();
        }
        System.out.println("----> iterator:");
        LinkIterator<String> iterator = linkList.iterator();
        while (iterator.hasNext()) {
            Link<String> link = iterator.getCurrent();
            link.display();
            System.out.println();
            if (link.data.equals("data_6")) {
                iterator.remove();
            }
            iterator.next();
        }
        linkList.display();
    }

5. 之前介绍栈时有提到可以使用链表实现：将ArrayStack中的数组替换为LinkList，push用insertFirst实现，pop用deleteFirst实现，也是完全可以的，实现代码如下：

public class LinkStack<T> extends Stack<T> {

    private LinkList<T> linkList;

    public LinkStack() {
        linkList =new LinkList();
    }

    @Override
    public boolean isEmpty() {
        return linkList.getFirst()==null;
    }

    @Override
    public void push(T value) {
        linkList.insertFirst(value);
    }

    @Override
    public T pop() {
        return linkList.deleteFirst().data;
    }

    @Override
    public T peek() {
        return linkList.getFirst().data;
    }

    @Override
    public void display() {
        System.out.print("LinkStacker: ");
        linkList.display();
    }
}

有序链表

• 数据项按照关键值有序排列
• 之前有用有序数组实现优先级队列，然而使用有序链表也是可以实现的
• 提供一种新的数组排序算法：表插入排序
  有序链表可以用于一种高效的排序机制，假设有一个无序数组，如果从这个数组中取出数据，然后一个一个的插入有序链表，他们自动的按顺序排列，把它们从有序表中删除，重新放入数组，那么数组就排好序了，这种排序方式比常用的插入排序效率更高些；
• 那么为什么不直接用有序数组呢？有序链表的插入效率要优于有序数组，因为不需要移动元素；而且链表所占用内存是充分利用的，而且扩充方便，不用担心角标越界问题；
• 有序链表的实现

public class OrderedLinkList<T extends Comparable<T>> extends LinkList<T> {
    public void insert(T value) {
        Link<T> newLink = new Link<>(value);
        Link<T> previous = null;
        Link<T> current = first;
        while (current != null && value.compareTo(current.data) > 0) {
            previous = current;
            current = current.next;
        }
        if (previous == null)
            first = newLink;
        else
            previous.next = newLink;
        newLink.next = current;
    }

    public Link<T> find(T value) {
        Link<T> current = first;
        while (current != null && current.data.compareTo(value) <= 0) {
            if (current.data == value)
                return current;
            current = current.next;
        }
        return null;
    }

    public Link<T> delete(T value) {
        Link<T> previous = null;//当前值的前一个链结点
        Link<T> current = first;//当前链结点
        while (current != null && current.data.compareTo(value) < 0) {
            previous = current;
            current = current.next;
        }
        if (current.data != value)
            return null;
        if (current == first)
            //如果所找的值对应first链结点，就把first指向下一个链结点，也就是first.next
            first = first.next;
        else
            //如果不是对应first，就把该链结点的前一个链结点的指针next指向该链结点的下一个链结点，即current.next
            previous.next = current.next;
        return current;
    }
}