[数据结构与算法]数据结构与算法-基础（二）单向链表

摘要

上期共同探究了下动态数组的添加、删除等实现方法，想要再回顾一下的话，点击我去再看看。接下来继续探究数组。

其实，动态数组有个明显的缺点，就是有可能造成内存空间的大量浪费。那么有什么办法可以做到用多少就给多少呢？这时，咱接着探究一下链表，看看能不能解决这个疑问。

链表

话入正题，先说一下链表。链表是线性存储的一种方式，每一个存放元素的内存空间不是相邻的，需要用锁链的方式去链接每一个存储元素的内存空间。

正因为内存空间不用相邻，所以在申请内存空间的时候，不需要多申请内存空间。

对比着具有连续的内存空间来存放元素，它在遍历查询上显的没有很高效方便，要根据不同的应用场景来选择。

Array 的常用 API

按照惯例，先来一组常用的数组 API，看过上期动态数组，直接跳到下一节（数据结构）

/**
 * 清除所有元素
 */
public void clear()
/**
 * 元素的数量
 * @return
 */
public int size()
/**
 * 是否为空
 * @return
 */
public boolean isEmpty()
/**
 * 是否包含某个元素
 * @param element
 * @return
 */
public boolean contains(E element)
/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element)
/**
 * 获取index位置的元素
 * @param index
 * @return
 */
public E get(int index)
/**
 * 设置index位置的元素
 * @param index
 * @param element
 * @return 原来的元素?
 */
public E set(int index, E element)
/**
 * 在index位置插入一个元素
 * @param index
 * @param element
 */
public void add(int index, E element)
/**
 * 删除index位置的元素
 * @param index
 * @return
 */
public E remove(int index)
/**
 * 删除元素
 * @param element
 */
public void remove(E element)
/**
 * 查看元素的索引
 * @param element
 * @return
 */
public int indexOf(E element)

数据结构

根据链表的性质来看，存储空间的位置不固定，需要类似锁链的东西来链接。所以就用到指针来做锁链，那么每一个存储空间就定义为节点。

除此之外，使用数组的时候，就需要确定一个头节点，来遍历寻找其他的元素，这里就设置为first。

锁链的本质，就是在节点中直接创建一个同类型的指针变量存放下一个节点的指针地址。

public class SingleLinkList<E> extends AbstractList<E>{

  // 头部节点
  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;
    }
}

实现方式

动态数组中一节中，咱先实现了可以直接处理的方法，比如元素的数量、是否为空。

然后根据在复杂方法中，先实现基础再组合实现其他方法逻辑实现了一些组合方法，比如是否包含某个元素、添加元素到尾部、删除元素。

/**
 * 元素数量
 */
protected int size = 0;

/**
 * 元素的数量
 * @return
 */
public int size() {
  return size;
}

/**
 * 是否为空
 * @return
 */
public boolean isEmpty() {
  return size == 0;
}

/**
 * 是否包含某个元素
 * @param element
 * @return
 */
public boolean contains(E element) {
  return indexOf(element) != ELEMENT_NOT_FOUND;
}

/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element) {
  add(size, element);
}

/**
 * 删除元素
 * @param element
 */
public void remove(E element) {
  remove(indexOf(element));
}

protected void outOfBound(int index) {
  throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
}

/**
 * 判断坐标是否越界
 * @param index
 */
protected void rangeCheck(int index) {
  if (index < 0 || index >= size) {
    outOfBound(index);
  }
}

protected void rangeCheckOfAdd(int index) {
  if (index < 0 || index > size) {
    outOfBound(index);
  }
}

链表实现方法

扯了这么久，终于进入今天的正题，通过链表来实现基础方法。

清除所有元素

在 JAVA 机制中，当一个内存空间没有被其他对象（节点）指着，就会自动释放。那么清除所有元素就非常简单, 直接让头节点为空即可，不要忘记把size设置为0.

	public void clear() {
		first = null;
		size = 0;
	}

获取 index 位置的元素

链表的数据结构中看到，元素是存放到节点的element数据中，链表中的节点也不是相邻的，所以就需要以first节点开始，通过遍历方法来获取。

这里先实现便利获取 index 位置的节点,在便利之前需要先判断index是否越界。

	/**
	 * 获取某个坐标的 node
	 * @param index
	 * @return
	 */
	private Node<E> node(int index) {
		rangeCheck(index);
		
		Node<E> node = first;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}

获取到节点，只需将节点中的元素取出即可

	public E get(int index) {
		return node(index).element;
	}

设置index位置的元素

上面已经实现了获取index的节点，那么只需要将这个节点的元素设置为新的元素就完成了。

/**
 * 设置index位置的元素
 * @param index
 * @param element
 * @return 原来的元素?
 */
public E set(int index, E element) {
  Node<E> node = node(index);
  E old = node.element;
  node.element = element;
  return old;
}

在index位置插入一个位置

实现这个方法，需要考虑两个不同的情况，1.数组中没有一个元素和2.数组中已经有元素。

1中的情况就直接把元素放在first节点中，2中的情况就需要先获取index-1位置的next节点，将这个next指向这个插入的节点，这个新插入的节点的next指向原来在index位置的节点，size不要忘记加1.

听着有些绕，直接上代码

public void add(int index, E element) {
  // 需要先做判断
  rangeCheckOfAdd(index);
  if (index == 0) {
    // 插入第一个，并不是说 first 就是 null。也是指向有值的
    first = new Node<>(element, first); 
  }
  else {
    Node<E> prev = node(index-1);
    Node<E> node = new Node<>(element, prev.next);
    prev.next = node;
  }
  size ++;
}

删除index位置的元素

这个方法同样需要考虑1.删除index=0位置元素和2.删除其他位置元素这两种情况。

若是1中情况，只需要将first节点指向它的下一个节点即可。若是2中情况，就先获取index-1位置节点，让这个节点的next指向index位置的next。index位置没有其他对象指引，就被直接删除（释放）。

public E remove(int index) {
  // 需要先判断
  rangeCheck(index);
  Node<E> old = first;
  if (index == 0) {
    // 只是删除对应的坐标，不是删除所有
    first = first.next;
  }
  else {
    Node<E> prev = node(index -1);
    old = prev.next;
    prev.next = prev.next.next;
  }
  size --;
  return old.element;
}

查看元素的索引

元素要看一下是否为 null，如果为 null，则无法进行比较，就遍历找第一个为 null 的元素。

public int indexOf(E element) {
  if (element == null) {
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
      if (node.element == null) {
        return i;
      }
      node = node.next;
    }
  }
  else {
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
      if (element.equals(node.element)) {
        return i;
      }
      node = node.next;
    }
  }
  return ELEMENT_NOT_FOUND;
}

整体实现

链表实现就完成了，链表中没有了索引的概念，取而代之的是类似指针的概念。在一些方法实现上和上一期动态数组一样，这里做了一些抽取，这里有包括抽取的方法，代码有些长，想着还是保证代码的完整性，不能自己实现的时候，缺这块缺那块的。

实现链表中的方法（本期重点）

public class SingleLinkList<E> extends AbstractList<E>{

	// 私有变量
	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;
		}
	}
	
	@Override
	public void clear() {
		first = null;
		size = 0;
	}

	@Override
	public E get(int index) {
		return node(index).element;
	}

	@Override
	public E set(int index, E element) {
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

	@Override
	public void add(int index, E element) {
		// 需要先做判断
		rangeCheckOfAdd(index);
		if (index == 0) {
			// 插入第一个，并不是说 first 就是 null。也是指向有值的
			first = new Node<>(element, first); 
		}
		else {
			Node<E> prev = node(index-1);
			Node<E> node = new Node<>(element, prev.next);
			prev.next = node;
		}
		size ++;
	}

	@Override
	public E remove(int index) {
		// 需要先判断
		rangeCheck(index);
		Node<E> old = first;
		if (index == 0) {
			// 只是删除对应的坐标，不是删除所有
			first = first.next;
		}
		else {
			Node<E> prev = node(index -1);
			old = prev.next;
			prev.next = prev.next.next;
		}
		size --;
		return old.element;
	}

	@Override
	public int indexOf(E element) {
		if (element == null) {
			Node<E> node = first;
			for (int i = 0; i < size; i++) {
				if (node.element == null) {
					return i;
				}
				node = node.next;
			}
		}
		else {
			Node<E> node = first;
			for (int i = 0; i < size; i++) {
				if (element.equals(node.element)) {
					return i;
				}
				node = node.next;
			}
		}
		return ELEMENT_NOT_FOUND;
	}
	
	/**
	 * 获取某个坐标的 node
	 * @param index
	 * @return
	 */
	private Node<E> node(int index) {
		rangeCheck(index);
		
		Node<E> node = first;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}
	
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("size:").append(size).append(" ").append("[");
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				stringBuilder.append(",");
			}
			stringBuilder.append(node.element);
			node = node.next;
		}
		stringBuilder.append("]");
		return stringBuilder.toString();
	}
}

继承公共实现方法

将通用的方法声明为公共方法，自定义的方法就可以继承这个公共类去实现。

public abstract class AbstractList<E> implements List<E> {

	/**
	 * 元素数量
	 */
	protected int size = 0;
	
	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {
		return size;
	}
	
	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	public void add(E element) {
		add(size, element);
	}
	
	/**
	 * 删除元素
	 * @param element
	 */
	public void remove(E element) {
		remove(indexOf(element));
	}
	
	protected void outOfBound(int index) {
		throw new IndexOutOfBoundsException("Index"+ index +", size" + size);
	}
	
	/**
	 * 判断坐标是否越界
	 * @param index
	 */
	protected void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfBound(index);
		}
	}
	
	protected void rangeCheckOfAdd(int index) {
		if (index < 0 || index > size) {
			outOfBound(index);
		}
	}
}

接口方法

这是 java 中的实现方式，将要实现的方法先做声明

public interface List<E> {

	/**
	 * 默认标示
	 */
	static final int ELEMENT_NOT_FOUND = -1;
	
	/**
	 * 清除所有元素
	 */
	public void clear();

	/**
	 * 元素的数量
	 * @return
	 */
	public int size();

	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty();

	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element);

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	public void add(E element);

	/**
	 * 获取index位置的元素
	 * @param index
	 * @return
	 */
	public E get(int index);

	/**
	 * 设置index位置的元素
	 * @param index
	 * @param element
	 * @return 原来的元素?
	 */
	public E set(int index, E element);

	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	public void add(int index, E element);

	/**
	 * 删除index位置的元素
	 * @param index
	 * @return
	 */
	public E remove(int index);
	
	/**
	 * 删除元素
	 * @param element
	 */
	public void remove(E element);

	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element);
}