链式线性表

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

package com.nonefly.list;
/**
 * 链式线性表（双向链表）
 * @author nonefly
 * @param <T>
 * 2015-5-1
 */
public class MyLinkList<T> implements MyList<T> {
    // LinkedList<E>
    private Node header;
    private Node tail;
    private int size = 0;

    public MyLinkList() {
        header = null;
        tail = null;
    }

    public int length() {
        return size;
    }

    public T get(int index) {
        if (index < 0 || index > size - 1)
            throw new IndexOutOfBoundsException("index");
        return getNodeByIndex(index).data;
    }

    private Node getNodeByIndex(int index) {
        // 根据index位置 选择从头/尾遍历 提高效率size >> 1 等于 size/2
        if (index < (size >> 1)) {// 从头遍历
            Node node = header;
            for (int i = 0; i < index; i++)
                node = node.next;
            return node;
        } else {// 后半部分，从尾遍历
            Node node = tail;
            for (int i = size - 1; i > index; i--)
                node = node.prev;
            return node;
        }
    }

    public int indexOf(T element) {
        // 这样写看起来代码简单，实则运算复杂度提高，因为每次循环if中会有大量比较判断
        /*
         * for (Node node = header; node != null; node = node.next) { if
         * ((node.data == null && element == null)//element为空时 || (element !=
         * null && element.equals(node.data)))//element不为空时 return index;
         * index++; } return -1;
         */
        int index = 0;
        // 所以还是分开写（也是源码中写法）
        if (element == null) {
            for (Node node = header; node != null; node = node.next) {
                if (node.data == null)
                    return index;
                index++;
            }
        } else {
            for (Node node = header; node != null; node = node.next) {
                if (element.equals(node.data))
                    return index;
                index++;
            }
        }
        return -1;
    }
    //指定位置插入
    public void insert(int index, T element) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("index");
        if(header == null)
            add(element);
        else
            addBefore(element, getNodeByIndex(index));
    }
    //在节点前添加元素
    private void addBefore(T element, Node n) {
        final Node pre = n.prev;
        final Node newNode = new Node(pre, element, n);//新节点
        if (pre == null)// 无前节点
            header = newNode;
        else
            pre.next = newNode;//前节点next->新节点
        n.prev = newNode;//下一节点prev->新节点
        size++;
    }

    // 尾插法
    public void add(T element) {
        final Node node = tail;
        final Node newNode = new Node(node, element, null);
        if (node == null)// 链表为空
            header = newNode;
        else
            node.next = newNode;
        tail = newNode;
        size++;
    }

    /**
     * 头插法
     * @param element
     */
    public void addHead(T element) {
        final Node node = header;
        final Node newNode = new Node(null, element, node);
        if (node == null)// 链表为空
            tail = newNode;
        else
            node.prev = newNode;
        header = newNode;
        size++;
        
    }

    public T delete(int index) {
        if (index < 0 || index > size - 1)
            throw new IndexOutOfBoundsException("index "+index);
        return unlink(getNodeByIndex(index));
    }
    //删除指定节点
    private T unlink(Node del) {
        final T data = del.data;
        final Node prev = del.prev;
        final Node next = del.next;
        if(prev == null){//删除节点为头结点
            header = next;
        }else{
            prev.next = next;
            del.prev = null;//将删除节点前驱置为空
        }
        if(next == null){//删除节点为尾结点
            tail = prev;
        }else{
            next.prev = prev;
            del.next = null;//将删除节点后继置为空
        }    
        del.data = null;//将删除节点数据置为空
        size--;
        return data;
    }

    public T remove() {
        return unlink(tail);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        //也许应该从头结点遍历置空所有节点？
        header = null;
        tail = null;
        size = 0;
    }
    @Override
    public String toString() {
        if(size == 0) return "[]";
        StringBuilder sb = new StringBuilder("[");
        for(Node node = header; node != null ; node = node.next)
            sb.append(node.data+", ");
        int len = sb.length();
        return sb.delete(len - 2, len).append("]").toString();
    }
    // 链表节点
    private class Node {
        T data;// 节点数据
        Node next;// 下一个节点
        Node prev;// 前一个节点

        public Node() {
        }

        Node(Node prev, T data, Node next) {
            this.prev = prev;
            this.data = data;
            this.next = next;
        }
    }
}