03_链表
2020-09-14 本文已影响0人
伶俐ll
- 动态数组有个明显的缺点：
可能会造成内存空间的大量浪费 - 能否用到多少就申请多少内存？
链表可以办到这一点
初识链表
链表是一种链式村粗的线性表，所有元素的内存地址不一定是连续的
Snip20200914_7.png
Snip20200914_8.png
接口设计
链表的接口和动态数组是一致的
int size(){} // 元素的数量boolean isEmpty(){} // 是否为空void add(E element){} // 添加元素到最后面void set(int index,E element){} // 设置index位置的元素void add(int index,E element){} // 在index位置插入一个元素void remove(int index){} // 删除index位置的元素boolean contains(E element){} // 是否包含某个元素E get(int index){} // 获取index位置的元素int indexOf(E element){} // 查看元素的索引void clear(){} // 清除所有元素
链表类型
依赖于指针
- 单向链表
- 单向循环链表
- 双向链表
- 双向循环链表
不依赖于指针 - 静态链表
有些编程语言是没有指针的，比如早期的BASIC、FORTRAN语言，那么在没有指针的情况下，如何实现链表？
- 静态链表，即通过数组模拟链表
数组的每个元素存放2个数据：值，下一个元素的索引，数组0位置存放的是头节点信息
Snip20200914_19.png
Snip20200914_20.png
如果数组的每一个元素只能存放1个数据，那么就使用2个数组，一个数组存放索引关系，一个数组存放值
代码实现
1. 单向链表
package LinkedList;
public class LZSingleLinkedList <E>{
/**
* 元素的数量
*/
private int size;
//第一个结点
private Node<E> first;
//结点元素
private static class Node<E>{
E element;
Node<E> next;
public Node(E element,Node<E> next){
this.element = element;
this.next = next;
}
}
/**
* 元素找不到
*/
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 添加元素到尾部
* @param element
*/
public void add(E element){
add(size,element);
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index,E element){
if (index<0 || index>size) {
outOfBounds(index);
}
//插入数据
if (index == 0){
first = new Node(element,first);
}else{
Node<E> preNode = node (index-1);
preNode.next = new Node<>(element,preNode.next);
}
size++;
}
/**
* 清除所有元素
*/
public void clear(){
first = null;
size = 0;
}
/**
* 删除index位置的元素
* @param index
*/
public void remove(int index){
rangeCheck(index);
if (index == 0){
first = first.next.next;
}else {
Node<E> preNode = node(index-1);
preNode.next = preNode.next.next;
}
size--;
}
/**
* 设置index位置的元素
* @param index
* @param element
*/
public void set(int index,E element){
rangeCheck(index);
Node<E> node = node(index);
node.element = element;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index){
rangeCheck(index);
return node(index).element;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
Node<E> node = first;
if (element == null){
for (int i = 0;i<size;i++){
if (node.element == null) return i;
node = first.next;
}
}else{
for (int i = 0;i<size;i++){
if (element.equals(node.element)) return i;
node = first.next;
}
}
return ELEMENT_NOT_FOUND;
}
private Node<E> node(int index){
rangeCheck(index);
Node<E> preNode = first;
for (int i = 0;i<index;i++){
preNode = preNode.next;
}
return preNode;
}
/**
* 检查下标越界
* @param index
* @return
*/
private void rangeCheck(int index){
if (index<0 || index >= size){
outOfBounds(index);
}
}
/**
* 检查到下标越界，抛出异常
* @param index
* @return
*/
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
Node<E> node = first;
while (node != null){
string.append(node.element);
node = node.next;
string.append(", ");
}
string.append("]");
return string.toString();
}
}
2. 单向链表增加虚拟头节点
有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟头节点（不存储数据）
Snip20200914_10.png
package LinkedList;
public class LZSingleLinkedList2 <E>{
/**
* 元素的数量
*/
private int size;
//第一个结点
private Node<E> first;
//结点元素
private static class Node<E>{
E element;
Node<E> next;
public Node(E element,Node<E> next){
this.element = element;
this.next = next;
}
}
private static final int ELEMENT_NOT_FOUND = -1;
public LZSingleLinkedList2(){
first = new Node(null,null);
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element){
add(size,element);
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index,E element){
if (index<0 || index>size) {
outOfBounds(index);
}
//插入数据
Node<E> preNode = index == 0?first: node (index-1);
preNode.next = new Node<>(element,preNode.next);
size++;
}
/**
* 清除所有元素
*/
public void clear(){
first = null;
size = 0;
}
/**
* 删除index位置的元素
* @param index
*/
public void remove(int index){
rangeCheck(index);
Node<E> preNode = index==0?first: node(index-1);
preNode.next = preNode.next.next;
size--;
}
/**
* 设置index位置的元素
* @param index
* @param element
*/
public void set(int index,E element){
rangeCheck(index);
Node<E> node = node(index);
node.element = element;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index){
rangeCheck(index);
return node(index).element;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
Node<E> node = first;
if (element == null){
for (int i = 0;i<size;i++){
if (node.element == null) return i;
node = first.next;
}
}else{
for (int i = 0;i<size;i++){
if (element.equals(node.element)) return i;
node = first.next;
}
}
return ELEMENT_NOT_FOUND;
}
private Node<E> node(int index){
rangeCheck(index);
Node<E> node = first.next;
for (int i = 0;i<index;i++){
node = node.next;
}
return node;
}
/**
* 检查下标越界
* @param index
* @return
*/
private void rangeCheck(int index){
if (index<0 || index >= size){
outOfBounds(index);
}
}
/**
* 检查到下标越界，抛出异常
* @param index
* @return
*/
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
Node<E> node = first.next;
while (node != null){
string.append(node.element);
node = node.next;
string.append(", ");
}
string.append("]");
return string.toString();
}
}
3. 双向链表
使用双向链表可以提升链表的综合性能
Snip20200914_12.png
当双向链表只有一个元素
Snip20200914_13.png
package LinkedList;
public class LZLinkedList <E>{
/**
* 元素的数量
*/
private int size;
/**
* 第一个结点
*/
private Node<E> first;
/**
* 最后一个结点
*/
private Node<E> last;
/**
* 结点
*/
private static class Node<E>{
E element;
Node<E> next;
Node<E> prev;
public Node(E element,Node<E> prev,Node<E> next){
this.element = element;
this.next = next;
this.prev = prev;
}
}
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 添加元素到尾部
* @param element
*/
public void add(E element){
add(size,element);
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index,E element){
if (index<0 || index>size) {
outOfBounds(index);
}
if(index == size) { //往最后面添加元素
Node<E> oldLast = last;
last = new Node<>(element, oldLast, null);
if (oldLast == null) { //这是链表的第一个元素
first = last;
} else {
oldLast.next = last;
}
}else{
Node<E> next = node (index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(element,prev,next);
next.prev = node;
if (prev == null){ // index == 0
first = node;
}else {
prev.next = node;
}
}
size++;
}
/**
* 清除所有元素
*/
public void clear(){
first = null;
last = null;
size = 0;
}
/**
* 删除index位置的元素
* @param index
*/
public void remove(int index){
rangeCheck(index);
Node<E> node = node(index);
Node prev = node.prev;
Node next = node.next;
if (prev == null){
first = next;
}else {
prev.next = next;
}
if (next == null){
last = prev;
}else {
next.prev = prev;
}
size--;
}
/**
* 设置index位置的元素
* @param index
* @param element
*/
public void set(int index,E element){
rangeCheck(index);
Node<E> node = node(index);
node.element = element;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index){
rangeCheck(index);
return node(index).element;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
Node<E> node = first;
if (element == null){
for (int i = 0;i<size;i++){
if (node.element == null) return i;
node = first.next;
}
}else{
for (int i = 0;i<size;i++){
if (element.equals(node.element)) return i;
node = first.next;
}
}
return ELEMENT_NOT_FOUND;
}
private Node<E> node(int index){
rangeCheck(index);
if (index>(size>>1)){ //从后向前找到节点
Node<E> node = last;
for (int i = size - 1;i >index ;i--){
node = node.prev;
}
return node;
}else { //从前向后找到节点
Node<E> node = first;
for (int i = 0;i<index;i++){
node = node.next;
}
return node;
}
}
/**
* 检查下标越界
* @param index
* @return
*/
private void rangeCheck(int index){
if (index<0 || index >= size){
outOfBounds(index);
}
}
/**
* 检查到下标越界，抛出异常
* @param index
* @return
*/
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
Node<E> node = first;
while (node != null && node.next != null){
string.append(node.element).append("-").append(node.next.element).append(" , ");
node = node.next;
}
string.append("]");
return string.toString();
}
}
4. 单向循环链表
Snip20200914_14.png
单向循环链表 - 只有1个节点
Snip20200914_15.png
package LinkedList;
public class LZSingleCircleLinkedList <E>{
/**
* 元素的数量
*/
private int size;
//第一个结点
private Node<E> first;
//结点元素
private static class Node<E>{
E element;
Node<E> next;
public Node(E element,Node<E> next){
this.element = element;
this.next = next;
}
}
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 添加元素到尾部
* @param element
*/
public void add(E element){
add(size,element);
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index,E element){
if (index<0 || index>size) {
outOfBounds(index);
}
//插入数据
if (index == 0){
Node<E> node = new Node(element,first);
Node<E> last = size == 0? node:node(size -1);
first = node;
last.next = node;
}else{
Node<E> preNode = node (index-1);
preNode.next = new Node<>(element,preNode.next);
}
size++;
}
/**
* 清除所有元素
*/
public void clear(){
first = null;
size = 0;
}
/**
* 删除index位置的元素
* @param index
*/
public void remove(int index){
rangeCheck(index);
if (index == 0){
if (size == 1){ //数组中只有一个元素
first = null;
}else {
first = first.next;
node(size - 1).next = first;
}
}else {
Node<E> preNode = node(index-1);
preNode.next = preNode.next.next;
}
size--;
}
/**
* 设置index位置的元素
* @param index
* @param element
*/
public void set(int index,E element){
rangeCheck(index);
Node<E> node = node(index);
node.element = element;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index){
rangeCheck(index);
return node(index).element;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
Node<E> node = first;
if (element == null){
for (int i = 0;i<size;i++){
if (node.element == null) return i;
node = first.next;
}
}else{
for (int i = 0;i<size;i++){
if (element.equals(node.element)) return i;
node = first.next;
}
}
return ELEMENT_NOT_FOUND;
}
private Node<E> node(int index){
rangeCheck(index);
Node<E> preNode = first;
for (int i = 0;i<index;i++){
preNode = preNode.next;
}
return preNode;
}
/**
* 检查下标越界
* @param index
* @return
*/
private void rangeCheck(int index){
if (index<0 || index >= size){
outOfBounds(index);
}
}
/**
* 检查到下标越界，抛出异常
* @param index
* @return
*/
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
Node<E> node = first;
do{
string.append(node.element);
node = node.next;
string.append(", ");
}while (node != first);
string.append("]");
return string.toString();
}
}
5. 双向循环链表
Snip20200914_16.png
双向循环链表 - 只有一个节点
Snip20200914_17.png
package LinkedList;
public class LZCircleLinkedList <E>{
/**
* 元素的数量
*/
private int size;
/**
* 第一个结点
*/
private Node<E> first;
/**
* 最后一个结点
*/
private Node<E> last;
/**
* 结点
*/
private static class Node<E>{
E element;
Node<E> next;
Node<E> prev;
public Node(E element,Node<E> prev,Node<E> next){
this.element = element;
this.next = next;
this.prev = prev;
}
}
private static final int ELEMENT_NOT_FOUND = -1;
/**
* 添加元素到尾部
* @param element
*/
public void add(E element){
add(size,element);
}
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index,E element){
if (index<0 || index>size) {
outOfBounds(index);
}
if(index == size) { //往最后面添加元素
Node<E> oldLast = last;
Node<E> node = new Node<>(element, oldLast, first);
if (oldLast == null) { //这是链表的第一个元素
node.prev = node.next = last = first = node;
// first = last;
// first.next = first;
// first.prev = first;
// first = node;
// last = node;
// node.next = node;
// node.prev = node;
} else {
last = node;
oldLast.next = node;
first.prev = node;
}
}else{
Node<E> next = node (index);
Node<E> prev = next.prev;
Node<E> node = new Node<>(element,prev,next);
next.prev = node;
prev.next = node;
if (prev == last){ // index == 0
first = node;
}
}
size++;
}
/**
* 清除所有元素
*/
public void clear(){
first = null;
last = null;
size = 0;
}
/**
* 删除index位置的元素
* @param index
*/
public void remove(int index){
rangeCheck(index);
if (size == 1){
first = last = null;
}else {
Node<E> node = node(index);
Node prev = node.prev;
Node next = node.next;
prev.next = node.next;
next.prev = node.prev;
if (node == first){ //如果删除的是第一个元素
first = next;
}
if (node == last){ //如果删除的是最后一个元素
last = prev;
}
}
size--;
}
/**
* 设置index位置的元素
* @param index
* @param element
*/
public void set(int index,E element){
rangeCheck(index);
Node<E> node = node(index);
node.element = element;
}
/**
* 元素的数量
* @return
*/
public int size(){
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 获取index位置的元素
* @param index
* @return
*/
public E get(int index){
rangeCheck(index);
return node(index).element;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element){
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 查看元素的索引
* @param element
* @return
*/
public int indexOf(E element){
Node<E> node = first;
if (element == null){
for (int i = 0;i<size;i++){
if (node.element == null) return i;
node = first.next;
}
}else{
for (int i = 0;i<size;i++){
if (element.equals(node.element)) return i;
node = first.next;
}
}
return ELEMENT_NOT_FOUND;
}
private Node<E> node(int index){
rangeCheck(index);
if (index>(size>>1)){ //从后向前找到节点
Node<E> node = last;
for (int i = size - 1;i >index ;i--){
node = node.prev;
}
return node;
}else { //从前向后找到节点
Node<E> node = first;
for (int i = 0;i<index;i++){
node = node.next;
}
return node;
}
}
/**
* 检查下标越界
* @param index
* @return
*/
private void rangeCheck(int index){
if (index<0 || index >= size){
outOfBounds(index);
}
}
/**
* 检查到下标越界，抛出异常
* @param index
* @return
*/
private void outOfBounds(int index){
throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
}
@Override
public String toString(){
StringBuffer string = new StringBuffer();
string.append("size = ").append(size).append("\n[");
Node<E> node = first;
do {
string.append(node.element).append("-").append(node.next.element).append(" , ");
node = node.next;
}while (node != first);
// for (int i = 0; i < size; i++) {
// if (i != 0) {
// string.append(", ");
// }
// string.append(node.element);
// node = node.next;
// }
string.append("]");
return string.toString();
}
}
如何发挥循环链表的最大威力
可以考虑增设1个成员变量、3个方法
- current ： 用于指向某个节点
- void reset()：让current指向头节点first
- E next()：让current往后走一步，也就是current = current.next
-
E remove()：删除current指向的节点，删除成功后让current指向下一个节点
Snip20200914_21.png
复杂度分析
- 添加
最好：O(1) 最坏：O(n) 平均：O(n) - 添加元素到结尾
最好：O(1) 最坏：O(1) 平均：O(1) - 删除
最好：O(1) 最坏：O(n) 平均：O(n) - 设置index位置的值
最好：O(1) 最坏：O(n) 平均：O(n) - 获取inde位置的值
最好：O(1) 最坏：O(n) 平均：O(n)
双向链表 vs 动态数组
-
复杂度对比
Snip20200914_22.png
-
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容来解决）
-
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存浪费
-
如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
-
如果频繁在头部进行添加、删除操作，建议选择使用双向链表（环形数组也可以）
-
如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
-
如果有频繁的查询操作（随机访问操作），建议选择使用动态数组
