一、顺序表

顺序表在内存中是数组的形式存储

类名	SequenceList
构造方法	SequenceList(int capacity)：创建容量为capacity的SequenceList对象
成员方法	1. public void clear()：空置线性表 2. public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false 3. public int length():获取线性表中元素的个数 4. public T get(int i):读取并返回线性表中的第i个元素的值 5. public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素 6. public void insert(T t):向线性表中添加一个元素t 7. public T remove(int i):删除并返回线性表中第i个数据元素。 8. public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
成员变量	1. private T[] eles：存储元素的数组 2.private int N:当前线性表的长度

//用来构造顺序表
public class SequenceList<T> implements Iterable{//存储元素的数组private T[] eles;//当前线性表的长度private int N;//获得当前容量private int capacity;//构造方法public SequenceList(int capacity) {//强制类型转化this.eles = (T[])new Object[capacity];//初始化长度N = 0;//获取当前顺序表的容量this.capacity = capacity;}//空置线性表public void clear() {for (int index = 0 ; index<getLength();index++){eles[index] = null;}this.N = 0;}//判断线性表是否为空，是返回true，否返回falsepublic boolean isEmpty() {return N==0;}//获取线性表中元素的个数public int getLength() {return N;}//获取线性表的容量public int getCapacity() {return capacity;}//读取并返回线性表中的第i个元素的值public T get(int i) {if (i <= 0 || i>=N){throw new RuntimeException("当前元素不存在");}return eles[i];}//在线性表的第i个元素之前插入一个值为t的数据元素public void insert(int i,T t) {//如果当前元素的数量等于当前数组的长度if(N==eles.length){//扩容resize(2*eles.length);}//将i索引处以及后面的元素全部向后移动for (int index = N;index>i;index--){eles[index] = eles[index-1];}eles[i] = t;N++;}//向线性表中添加一个元素tpublic void insert(T t) {//如果当前元素的数量等于当前数组的长度if(N==eles.length){//扩容resize(2*eles.length);}//先将N处赋值为t，随后N自增eles[N]=t;N++;}//删除并返回线性表中第i个数据元素public T remove(int i) {//记录i处索引的值，并且后面的值全部向前移动T current = eles[i];for (int index = i ; index<N-1; index++ ){eles[index] = eles[index+1];}//元素个数减一N--;//如果当前元素的数量等于当前（数组的长度/4）if(N<eles.length/4){//将顺序表的长度变为原来的一半resize(eles.length/2);}return current;}//根据参数的newSize，重新来设置数组的大小public void resize(int newSize){//定义一个临时数组，指向原数组，用来提供复制数组T[] temp = eles;//容量翻倍eles = (T[]) new Object[newSize];//把原数组的数据拷贝到新数组即可for (int i = 0 ; i<N;i++){eles[i] = temp[i];}//重新定义容量的大小capacity = newSize ;}//返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返 回-1。public int indexOf(T t){if(t==null){throw new RuntimeException("查找的元素不合法");}for (int i = 0; i < N; i++) {if (eles[i].equals(t)){return i;}}return -1;}//实现遍历输出@Overridepublic Iterator iterator() {return new SIterator();}private class SIterator implements Iterator{private int index;public SIterator(){this.index = 0;}@Overridepublic boolean hasNext() {//表示还有下一个元素return index<N;}@Overridepublic Object next() {return eles[index++];}}
}

• 从以上代码可得知，顺序表查找元素很快，只需要进行一次遍历即可，时间复杂度为O(1);
• 在插入或者删除元素的时候，我们要进行相应的元素移动，时间复杂度大，时 间复杂为O(n);

二、链表

链表分为两个类组成，分别为Node节点类和LinkList链表类

2.1 单向链表

---

2.1.1 设计Node节点类

类名	Node
构造方法	Node(T t,Node next)：创建Node对象
成员变量	T item:存储数据 Node next：指向下一个结点

//用来定义节点
public class Node<T> {//存储数据T item;//下一个节点Node next;public Node(T item, Node next) {this.item = item;this.next = next;}
}

2.1.2 设计LinkList链表类

类名	LinkList
构造方法	LinkList()：创建LinkList对象
成员方法	1. public void clear()：空置线性表 2. public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false 3. public int length():获取线性表中元素的个数 4. public T get(int i):读取并返回线性表中的第i个元素的值 5. public void insert(T t)：往线性表中添加一个元素； 6. public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。 7. public T remove(int i):删除并返回线性表中第i个数据元素。 8. public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则 返回-1。
成员内容类	private class Node:结点类
成员变量	1. private Node head:记录首结点 2.private int N:记录链表的长度

//实现链表的构造
public class LinkList<T> implements Iterable{//记录头节点private Node<T> head;//记录链表的长度private int N;//构造方法public LinkList(){//初始化头节点this.head = new Node<T>(null,null);//初始化元素个数this.N = 0;}//清空链表：原理是断开头节点的指向，并且将链表置零public void clear(){head.next = null;}//获取链表的长度public int length(){return N;}//判断链表是否为空public boolean isEmpty(){return N==0;}//获取指定位置i处的元素public T get(int i){Node n = head.next;for (int index = 0 ; index<i ; index++){n = n.next;}return (T) n.item;}//向链表中插入元素public void insert(T t){//找到当前的最后一个节点Node n = head;while (n.next!=null){n = n.next;}//创建节点，保存元素Node newNode = new Node(t,null);//让当前最后一个节点指向新节点n.next = newNode;//元素的个数++N++;}//向链表的指定位置插入元素public void insert(int i , T t){if (i<0 || i>=N){throw new RuntimeException("位置不合法");}//找到i-1和i节点Node preNode = head;// i-1 节点for (int index = 0 ; index<=i-1 ; index++){preNode = preNode.next;}Node currentNode = preNode.next;// i 节点//创建新节点newNodeNode newNode = new Node(t,null);//让i-1节点的next节点指向创建的newNodepreNode.next = newNode;//将newNode的next节点指向原本的i节点newNode.next = currentNode;//元素个数++N++;}//删除指定位置的索引，并且返回被删除的元素public T remove(int i){if (i<0 || i>=N){throw new RuntimeException("位置不合法");}//找到 i-1 、 i 、i+1 节点Node preNode = head ; //找到i-1for (int index = 0 ; index<=i-1 ; index++){preNode = preNode.next;}Node currentNode = preNode.next; //找到iNode nextNode = currentNode.next; //找到i+1//将i-1的next节点指向i+1即可preNode.next = nextNode ;//元素个数--N--;return (T) currentNode.item;}//查找元素t在链表中第一次出现的位置public int indexOf(T t){Node n = head ;//依次去除节点元素进行比较for (int i = 0;n.next!=null;i++){n = n.next;if (t.equals(n.item)){return i;}}return -1;}//实现遍历输出@Overridepublic Iterator iterator() {return new LIterator();}public class LIterator implements Iterator{private Node n;public LIterator(){this.n = head;}@Overridepublic boolean hasNext() {return n.next!=null;}//获取下一个元素的值@Overridepublic Object next() {n = n.next;return n.item;}}
}

2.2 双向链表

---

2.2.1 设计Node节点类

类名	Node
构造方法	Node(T t,Node next)：创建Node对象
成员变量	T item:存储数据 Node next：指向下一个结点 Node pre：指向上一个结点

public class Node<T> {//下一个节点public Node next;//上一个节点public Node pre;//存储数据public T item;//构造函数public Node(Node pre, Node next, T item) {this.pre = pre;this.next = next;this.item = item;}
}

2.2.2 设计DoublyLinkList链表类

类名	DoublyLinkList
构造方法	DoublyLinkList()：创建DoublyLinkList对象
成员方法	1. public void clear()：空置线性表 2. public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false 3. public int length():获取线性表中元素的个数 4. public T get(int i):读取并返回线性表中的第i个元素的值 5. public void insert(T t)：往线性表中添加一个元素； 6. public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。 7. public T remove(int i):删除并返回线性表中第i个数据元素。 8. public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。 9. public T getFirst():获取第一个元素 10. public T getLast():获取最后一个元素
成员内容类	private class Node:结点类
成员变量	1. private Node head:记录首结点 2. private Node end:记录尾结点 3.private int N:记录链表的长度

public class DoublyLinkList<T> implements Iterable{//记录头节点private Node<T> head;//记录尾节点private Node<T> end;//记录链表的长度private int N;//构造方法public DoublyLinkList(){//初始化头节点和尾节点this.head = new Node<T>(null,null,null);this.end = null;//所以这个地方头节点和尾节点不占用长度this.N = 0;}//清空链表：原理是断开头节点和尾节点的指向，并且将链表置零public void clear(){head.next = null;end = null;N = 0;}//获取链表的长度public int length(){return N;}//判断链表是否为空public boolean isEmpty(){return N==0;}//获取第一个元素public T getHead(){if (isEmpty()){return null;}return (T) head.next.item;}//获取最后一个元素public T getLast(){if (isEmpty()){return null;}return (T) end.item;}//向链表中插入元素(默认是尾部)public void insert(T t){//1. 如果链表为空if (isEmpty()){//1.1 创建新的节点Node newNode = new Node(head, null, t);//1.2 让新的的节点称之为尾节点end = newNode;//1.3 让头节点指向尾节点head.next = end;}else {//2. 如果链表不为空Node oldNode = end;//2.1 创建新的节点Node newNode = new Node(oldNode,null,t);//2.2 让当前的尾节点指向新节点oldNode.next = newNode;//2.3 让新节点成为尾节点end = newNode;}N++;}//向链表的指定位置插入元素public void insert(int i , T t){if (i<0 || i>=N){throw new RuntimeException("位置不合法");}//找到 i-1 的节点//假如在 3 位置插入新节点，我们就是遍历从0-2，恰好可以找到2节点Node preNode = head;for (int index = 0 ; index<=i-1 ; index++){preNode = preNode.next;}//找到 i 位置节点Node currentNode = preNode.next;//创建新节点Node newNode = new Node(null,null,t);//修改指向preNode.next = newNode;newNode.next = currentNode;currentNode.pre = newNode;newNode.pre = preNode;//元素个数加一N++;}//删除指定位置的索引，并且返回被删除的元素public T remove(int i){if (i<0 || i>=N){throw new RuntimeException("位置不合法");}//找到i位置的节点Node node = head;for (int index = 0 ;index<=i ; index++){node = node.next;}//找到 i+1 位置节点Node nextNode = node.next;//找到 i-1 位置节点Node preNode = node.pre;//修改指向preNode.next = nextNode;nextNode.pre = preNode;N--;return (T) node.item;}//获取指定位置i处的元素public T get(int i){Node node = head;for (int index = 0 ; index<=i ; index++){node  = node.next;}return (T) node.item;}//查找元素t在链表中第一次出现的位置public int indexOf(T t){Node node = head;for (int index = 0 ; node.next != null ; index++){node  = node.next;if (t.equals(node.item)){return index;}}return -1;}@Overridepublic Iterator iterator() {return new DIterator();}private class DIterator implements Iterator{private Node n;public DIterator() {this.n = head;}@Overridepublic boolean hasNext() {return n.next != null;}@Overridepublic Object next() {n = n.next;return n.item;}}
}

2.2.3 总结和提醒

---

总结

• 每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)
• 对于插入和移除节点，随着数据元素N的增多，查找的 元素越多，时间复杂度为O(n);
• 相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的， 它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作,同时它并没有涉及的元素的交换。

提醒

其中对于双向链表遍历的边界值条件，如下代码

//获取指定位置i处的元素
public T get(int i){Node node = head;for (int index = 0 ; index<=i ; index++){node  = node.next;}return (T) node.item;
}

我们需要获取到i处的元素，因为我们是从头节点head开始遍历，所以其实我们的跳数也是从头节点开始计算，假设我们需要定位到2号节点，从head节点开始计算，index设置为0，我们刚好要移动3次。即要定位i处的元素，边界值判定条件恰好为i

参考

黑马程序员Java数据结构与java算法全套教程