什么是线性表

线性表是最基本、最简单和最常用的一种数据结构，一个线性表是n个具有相同特性的数据元素的有限序列。
若A元素在B元素前面，则称A为B的前驱元素；若B元素在A元素的后面，则称B为A的后继元素。
线性表的特征：数据元素之间存在一对一的关系
第一个数据元素没有前驱元素，叫头结点。
最后一个数据元素没有后继元素，叫尾结点。
除了头尾结点，其它数据元素有且仅有一个前驱元素和后继元素。

线性表的分类

按照数据的存储方式可以分为顺序表和链表。

什么是链表

链表中的元素在内存中不连续，查询慢（查询任何数据都要从头开始找），但增删快，分为单链表和双链表。

本节内容包括单链表和双链表的实现、链表反转、快慢指针、循环链表（尾结点指向第一个数据结点）、约瑟夫问题。

码农浅知-Java数据结构线性表中单链表和双链表的实现

单链表实现

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
//注意此实现并不绝对严谨
import java.util.Iterator;

public class LinkList<T> implements Iterable<T> {
    //1、记录头结点
    private Node head;
    //2、记录链表的长度
    private int N;

    //3、结点内部类
    private class Node {
        T item; //数据
        Node next;  //下一个结点

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    //4、构造函数
    public LinkList() {
        //初始化头结点
        this.head = new Node(null, null);
        //初始化链表长度
        this.N = 0;
    }

    //5、清空链表
    public void clear() {
        head.next = null;
        this.N = 0;
    }

    //6、判断链表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //7、获取链表的长度
    public int length() {
        return N;
    }

    //8、获取指定位置i处的元素
    public T get(int i) {
        //从头结点开始遍历i次（严格来说要考虑空指针的情况）
        Node n = head;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return n.item;
    }

    //9、向链表中添加元素t
    public void add(T t) {
        //找到当前最后一个结点
        Node n = head;
        while (n.next != null) {
            n = n.next;
        }
        //创建新结点保存元素t
        Node newNode = new Node(t, null);
        //指向新结点，元素个数 +1
        n.next = newNode;
        this.N++;
    }

    //10、向指定位置i处添加元素t
    public void insert(int i, T t) {
        //找到i位置前一个结点
        Node pre = head;
        for (int index = 0; index < i - 1; index++) {
            pre = pre.next;
        }
        //i位置的结点
        Node temp = pre.next;
        //创建新结点保存元素t，并指向原i处结点
        Node tNode = new Node(t, temp);
        //前一结点指向新结点tNode
        pre.next = tNode;
        //元素个数 +1
        this.N++;
    }

    //11、删除指定位置i处的元素，并返回被删除的元素
    public T remove(int i) {
        //找到i位置前一个结点
        Node pre = head;
        for (int index = 0; index < i - 1; index++) {
            pre = pre.next;
        }
        //找到i位置结点
        Node temp = pre.next;
        //i位置前一个结点指向i位置后一个结点
        pre.next = temp.next;
        //元素个数 -1
        this.N--;
        return temp.item;
    }

    //12、查找元素t在链表中第一次出现的位置
    public int indexOf(T t) {
        Node n = head;
        for (int i = 1; n.next != null; i++) {
            n = n.next;
            if (n.item.equals(t)) {
                return i;
            }
        }
        return -1;
    }
    //13、遍历

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator {
        private Node n;

        public LIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }

    //14、链表反转
    public void reverse() {
        //判断是否为空
        if (isEmpty()) {
            return;
        }
        reverse(head.next);
    }

    public Node reverse(Node curr) {
        if (curr.next == null) {
            head.next = curr;
            return curr;
        }
        //递归反转curr的下个结点，返回值就是链表反转后当前结点的上一结点
        Node pre = reverse(curr.next);
        pre.next = curr;
        curr.next = null;
        return curr;
    }
}

双链表实现

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
//注意此实现并不绝对严谨
import java.util.Iterator;

public class TwoWayLinkList<T> implements Iterable<T> {
    //1、记录头尾结点
    private Node head;
    private Node last;
    //2、记录链表的长度
    private int N;

    //3、结点内部类
    private class Node {
        T item; //数据
        Node pre;   //上一个结点
        Node next;  //下一个结点

        public Node(T item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    //4、构造函数
    public TwoWayLinkList() {
        //初始化头结点和尾结点
        this.head = new Node(null, null, null);
        this.last = null;
        //初始化链表长度
        this.N = 0;
    }

    //5、清空链表
    public void clear() {
        head.next = null;
        last = null;
        this.N = 0;
    }

    //6、判断链表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //7、获取链表的长度
    public int length() {
        return N;
    }

    //8、获取第一个元素
    public T getFirst() {
        if (isEmpty()) {
            return null;
        }
        return head.next.item;
    }

    //9、获取最后一个元素
    public T getLast() {
        if (isEmpty()) {
            return null;
        }
        return last.item;
    }

    //10、获取指定位置i处的元素
    public T get(int i) {
        //从头结点开始遍历i次（严格来说要考虑空指针的情况）
        Node n = head;
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return n.item;
    }

    //11、向链表中添加元素t
    public void add(T t) {
        //链表为空
        if (isEmpty()) {
            //创建新结点（即尾结点），头结点指向新结点
            Node newNode = new Node(t, head, null);
            head.next = newNode;
            last = newNode;
        } else {
            //链表不为空
            //创建新结点，原尾结点指向新结点，新结点成为尾结点
            Node newNode = new Node(t, last, null);
            last.next = newNode;
            last = newNode;
        }
        //元素个数 +1
        this.N++;
    }

    //12、向指定位置i处添加元素t
    public void insert(int i, T t) {
        //找到i位置前一个结点
        Node pre = head;
        for (int index = 0; index < i - 1; index++) {
            pre = pre.next;
        }
        //i位置的结点
        Node temp = pre.next;
        //创建新结点保存元素t
        Node tNode = new Node(t, pre, temp);
        //原i处前一结点指向新结点tNode，原i处结点指向新结点
        pre.next = tNode;
        temp.pre = tNode;
        //元素个数 +1
        this.N++;
    }

    //13、删除指定位置i处的元素，并返回被删除的元素
    public T remove(int i) {
        //找到i位置前一个结点
        Node pre = head;
        for (int index = 0; index < i - 1; index++) {
            pre = pre.next;
        }
        //找到i位置结点
        Node temp = pre.next;
        //找到i位置下一个结点
        Node nextNode = temp.next;
        //i位置前一个结点指向i位置后一个结点
        pre.next = nextNode;
        //i位置后一个结点指向i位置前一个结点
        if (nextNode != null) {
            nextNode.pre = pre;
        }
        //元素个数 -1
        this.N--;
        return temp.item;
    }

    //14、查找元素t在链表中第一次出现的位置
    public int indexOf(T t) {
        Node n = head;
        for (int i = 1; n.next != null; i++) {
            n = n.next;
            if (n.item.equals(t)) {
                return i;
            }
        }
        return -1;
    }
    //15、遍历

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator {
        private Node n;

        public LIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}