一、链表
-
动态数组有个明显的缺点
- 可能会造成内存空间的大量浪费
-
能否用到多少就申请多少内存?
- 链表可以办到这一点
-
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
链表
二、链表的设计
链表的设计
public class LinkedList<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;
}
}
}
三、链表的接口设计
链表的大部分接口和动态数组是一致的
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
boolean contains(E element); // 是否包含某个元素
void add(E element); // 添加元素到最后面
E get(int index); // 返回index位置对应的元素
E set(int index, E element); // 设置index位置的元素
void add(int index, E element); // 往index位置添加元素
E remove(int index); // 删除index位置对应的元素
int indexOf(E element); // 查看元素的位置
void clear(); // 清除所有元素
那么链表和动态数组的很多接口是一样的，就可以设计一个接口List。
但是有一部分接口的实现是相同的(size、isEmpty、contains、add)，有些接口的实现是不相同的，于是可以在抽象一个父类AbstractList来实现链表和动态数组相同接口实现。
List接口：
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
boolean contains(E element); // 是否包含某个元素
void add(E element); // 添加元素到最后面
E get(int index); // 返回index位置对应的元素
E set(int index, E element); // 设置index位置的元素
void add(int index, E element); // 往index位置添加元素
E remove(int index); // 删除index位置对应的元素
int indexOf(E element); // 查看元素的位置
void clear(); // 清除所有元素
}
AbstractList类实现：
public abstract class AbstractList<E> implements List<E>{
protected int size;
/**
* 元素的数量
* @return
*/
@Override
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
@Override
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
@Override
public void add(E element) {
add(size,element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
四、清空元素 - clear()
清空元素
- 清空元素只需要将
first置为null就可以了，然后size置为0。 -
next是不需要置为null的,因为first = null后，first置为null之前的元素是没有GCRoot引用的，会被GC自动回收。
public void clear() {
first = null;
size = 0;
}
五、添加元素 - add(int index,E element)
findNode(int index)
如果想添加一个元素，得先找到要添加元素位置的前一个元素才可以完成，所以这里先实现一个findNode方法用于根据索引查找对应的元素
/**
* 获取index位置对应的节点对象
* @param index
* @return
*/
private Node<E> findNode(int index){
rangeCheck(index);
Node<E> node = first;
for(int i=0;i < index;i++) {
node = node.next;
}
return node;
}
add(int index,E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
if(index == 0) {
first = new Node<E>(element, first);
}else {
Node<E> prev = findNode(index - 1);
prev.next = new Node<E>(element, prev.next);
}
size++;
}
在编写链表过程中，要注意边界测试，比如 index 为 0 、size – 0 、size 时
六、获取和设值 - get(ind index)、set(int index,E element)
上面findNode方法实现了，那么对应的get和set方法也可以实现了。
public E get(int index) {
return findNode(index).element;
}
public E set(int index, E element) {
Node<E> node = findNode(index);
E old = node.element;
node.element = element;
return old;
}
七、删除元素 - remove(int index)
public E remove(int index) {
rangeCheck(index);//如果链表中没有数据
Node<E> node = first;
if(index == 0) {
first = first.next;
}else {
Node<E> prev = findNode(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
八、查看元素的索引 - indeOf(E element)
/**
* 查看元素的索引
* @param element
* @return
*/
@Override
public int indexOf(E element) {
if (element == null) { // 1
for (int i = 0; i < size; i++) {
Node<E> node = first;
if (node.element == null) return I;
node = node.next;
}
} else {
for (int i = 0; i < size; i++) {
Node<E> node = first;
if (element.equals(node.element)) return I;
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}
九、推荐一个神奇的网站
数据结构和算法动态可视化
网友评论