java-数据结构-链表

java-数据结构-链表 单链表

​

结点：由数据域和指针域组成

​

链表长什么样子？（大概这样）

​

后继与前驱： 例如上图a1是a2 的前驱，a3是a2的后继。

头结点和头（尾）指针：头结点是指链表的第一个结点（例如上图中的a1）、

头指针（head）：是仅仅是一个引用变量，储存头结点地址的指针而已。

尾指针（tail）：是链表中最后一个结点的指针。

链表的 *** 作 添加元素

1.当链表为空时，将头指针和尾指针都指向新增结点。如图

                                      

 2.链表中有元素，在表头添加元素，先将新增结点的指针域指向原链表的首结点，然后将头指针指向新增结点。此时的新增结点就是新的头结点。如图

                    

3.在链表的表尾添加，先将尾结点的指针域（不是尾指针）指向新增结点，然后再将尾指针指向新增结点。

                 

 3.在链表中添加，如图假如我们想在2这个结点后添加一个结点，则先将结点2 的指针域为空，然后在让新增的这个结点的指针域指向3结点，然后2的指针域指向新增的这个结点。

 将2结点的指针域为null

将新增结点的指针域指向结点3

将结点2 的指针域指向新增结点

 删除 *** 作

1.在表头删除结点，先将头指针指向下一个结点（此时下一个结点即将成为首结点），然后再将原首结点的指针域为空。

将原首结点的指针域为空

 2.在表尾删除结点，先定义一个p指针，让p指向最后一个结点（假设将最后一个几点设为n）的前一个结点（n-1），然后将n-1结点的指针为空，再将尾指针指向n-1结点。

 将尾指针指向n-1结点

 3.在链表中删除，假定，我们要删除第四个结点，还是定义一个p指针，将p指向删除结点的前一个结点（也就是结点3），先将结点3 的指针域指向结点5，然后再将删除的结点的指针域为null。

 

 将结点3的指针域指向结点5

 删除的指针域为null

 链表的选择排序

排序问题（从小到大）：先新定义两个nodeA,nodeB指针，nodeA指向首结点，nodeB指向第二个结点，，然后比较这两个指针所指的结点的数据域的大小，若nodeB比nodeA小，则交换数据域

。

 第二圈比较，重复 *** 作

 获得子链表

 获得2到5的子链表

先创建两个指针，分别为nodeA，nodeB，分别指向结点2和结点5，然后在定义一个指针p，将指针p=指针nodeA，在创建一个链表，用while循环，将各个几点添加到新链表中

 代码

 

public class linkedStringlyList implements LinearTable {

    //定义结点对象
    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 linkedStringlyList() {
        head = null;
        tail = null;
        size = 0;
    }

    public linkedStringlyList(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");
        }

        linkedStringlyList list = new linkedStringlyList();
        
        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) 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;
        }}
}