数据结构2-链表的实现

1.2 链表手动实现

1.介绍

动态数组缺点：可能会造成内存空间的大量浪费

• 链表能做到用多少就申请多少内存
• 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

  1.ArrayList与LinkedList 有许多相同的方法名(add, remove, size，clear等)，
  写一个接口List，封装这些相同的方法 -> public interface List<E>{}
  2.又他俩有几个相同的方法，方法内部代码也同（如rangeCheck，size，isEmpty等），
  弄个父类AbstractList，封装这些方法，让他俩都继承AbstractList。
  3.AbstractList作为父类 最后去实现List接口。
  4.由于父类只想放具有相同代码的方法，对于List接口里的那些只有方法名相同的方法，
  不想去实现，所以AbstractList 定义为abstract（抽象的）

public interface List<E>{}
public abstract class AbstractList<E> implements List<E>{}
public class MyLinkedList<E> extends AbstractList<E>{}
public class MyArrayList<E> extends AbstractList<E>{}

//调用
MyArrayList<Integer> list1 = new MyArrayList<>();
MyLinkedList<Integer> list2 = new MyLinkedList<>();
//或
List<Integer> list1 = new MyArrayList<>();
List<Integer> list2 = new MyLinkedList<>();

---

2.List接口

public interface List<E> {
	static final int ELEMENT_NOT_FOUND = -1; //元素未找到
	void clear();              //清除所有元素
	int size();                //获取元素数量
	boolean isEmpty();         //是否为空
	E get(int index);          //获取某个位置元素
	E set(int index, E element);    //修改，返回原来的元素
	void add(int index, E element);	//在index处插入一元素
	void add(E element);	        //添加元素到尾部
	void remove(int index);         //删除元素
	int indexOf(E element);         //查元素索引
	boolean contains(E element);    //是否包含某元素
}

---

3.AbstractList 父类，抽象类

public abstract class AbstractList<E> implements List<E> {
    protected int size;  //元素数量（protected 代表可以给子类使用）
	
    protected void rangeCheck(int index){ //判断是否越界
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
        }
    }
    private void rangeCheckForAdd(int index){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size);
        }
    }

	public int size(){
		return size;
	}

	public boolean isEmpty(){
		return size == 0;
	}

	public boolean contains(E element){
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	public void add(E element){
		add(size, element);
	}
}

---

4.常量

static final int ELEMENT_NOT_FOUND = -1; //元素未找到
因为需要外界调用ELEMENT_NOT_FOUND，即它要对外界可见，所以不能放在AbstractList中.
要放在list里面,由于接口里面的东西都是公共的，所以不用加public
AbstractList 属于中间人，对外界不可见（外界不能调用）
如对外界可见的则三个类：
List<Integer> list1 = new MyArrayList<>();
List<Integer> list2 = new MyLinkedList<>();

---

5.链表设计1 - 结点实现

// 在MyArrayList类里定义以下

private Node<E> first; // 首结点
	
// 结点：私有的内部类
private static class Node<E>{
    E element;        // 元素
    Node<E> nextNode; // 下一个Node
    
    public Node(E element, Node<E> nextNode) { // 构造方法
        this.element = element;
        this.nextNode = nextNode;
    }
}

---

6.清空链表 - (和ArrayList清空方式不同)

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

---

6.返回索引对应的结点对象

private Node<E> node(int index){
    rangeCheck(index); //先检查索引是否正确
    
    Node<E> node = first; //第一个结点
    
    for(int i = 0; i < index; i++) { //一共需要查index次（想想为啥）
        node = node.nextNode;
    }
    
    return node;
}

---

7.获取index位置元素(首先要找到结点)

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

---

8.设置index位置元素

public E set(int index, E element) {
    Node<E> node = node(index);  //获取结点
    E oldElement = node.element; //存结点元素
    node.element = element; //更新结点元素
    return oldElement;
}

---

9.添加(要注意0位置 试分析添加到末尾，为什么能通过)

public void add(int index, E element) {
    rangeCheckForAdd(index); //先检查索引是否正确

    if(index == 0) {
        first = new Node<E>(element, first);
    }else {
        Node<E> prevNode = node(index - 1);   //previous 先前的，以前的	
        //创建新结点(新结点next指向 index处结点) 
        //前一个结点的next指向新结点
        prevNode.nextNode = new Node<E>(element, prevNode.nextNode); 
    }
    
    size++; //这一步不能少
}

---

10.删除 (注意0位置)

public void remove(int index) {
    rangeCheck(index); //先检查索引是否正确
    
    if(index == 0) {
        first = first.nextNode;
    }else {
        Node<E> prevNode = node(index - 1);
        prevNode.nextNode = prevNode.nextNode.nextNode;
    }
    
    size--; //这一步不能少
}

---

11.查元素对应的索引(涉及到遍历链表)

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.nextNode; //去下一个结点
        }
    }else {
        Node<E> node = first;
        for(int i = 0; i < size; i++){
            if(element.equals(node.element)){
                return i;
            }
            node = node.nextNode;
        }
    }
    return ELEMENT_NOT_FOUND;
}

---

12.重写toString

public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [");
    
    Node<E> node = first;

    for(int i = 0; i < size; i++){
        if(i != 0){      //不是第一个元素，加个逗号
            string.append(", ");
        }
        string.append(node.element);
        
        node = node.nextNode;
    }
    string.append("]");
    return string.toString();
}

---

13.测试

List<Integer> list = new MyLinkedList<>();
		
list.add(10);
list.add(0, 20); //覆盖开头
list.add(30);
list.add(list.size(), 40); //加到末尾

System.out.println(list.toString());

//输出：size=4, [20, 10, 30, 40]

---

软法动态演示

---

赏

失败是成功之母

支付宝

微信