1.链表基础
- 链表是数据结构中另一种最基础的数据结构，数组需要开辟一段连续的存储空间，所以在初始化的时候需要指定大小，而链表并不需要指定大小，只要有足够的空间都可以不断地添加元素
- 链表适合于增删比较频繁的数据，而数据更适用于改动少，查询操作频繁的情况，在根据索引查询的时候可以快速定位
- 链表不存在存储空间不足的情况(除物理分配内存不足)，而java中也有由链表为底层数据结构实现的数据结构，支持泛型，即LinkedList(双向链表)
- 根据链表在本文实现一个单向链表，模拟LinkedList方法实现
2.实现
2.1.定义节点
- 定义一个私有内部类，代表链表中的每一个节点，而每一个结点中又定义下一个节点，以替代指针，同时使每个节点连接起来。
public class LinkedList<E> {
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) { this(e, null); }
public Node() { this(null, null); }
@Override
public String toString() { return e.toString(); }
}
//链表头
private Node dummyHead;
private int size;
public LinkedList() {
//虚拟头节点指向真正的头节点
dummyHead = new Node(null, null);
size = 0;
}
/**
* 获取链表中的元素个数
* @return ：
*/
public int getSize() { return size; }
/**
* 当前链表是否为空
* @return ：
*/
public boolean isEmpty() { return size == 0; }
采用设立一个虚拟头节点，这样就不要单独处理头节点，即初始化时，初始一个空结点，而而这个虚拟头节点指向存储的第一个非空结点。
2.2.添加一个新节点
- 新添一个节点，需要找到新添节点位置的前一个节点，使前一个节点的指针指向新添加的节点，而前一个节点原来指向的节点，变成新添加节点指向的节点
/**
* 在链表的index(0-based)位置添加新元素e
* @param index ：插入链表新元素的索引位置
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index");
}
//代表待添加节点索引的上一个节点，初始指向虚拟头节点
Node prev = dummyHead;
//找到要插入位置的上一个元素(前结点)
for (int i = 0; i < index; i++) {
prev = prev.next;
}
//将前结点的next结点当作新结点的next,再将新结点作为前结点的next实现插入
prev.next = new Node(e, prev.next);
size++;
}
/**
* 向链表中添加元素：
* 在链表头添加新元素，新元素索引指向当前链表头，当前链表头指针指向新添加元素
* @param e ：
*/
public void addFirst(E e) { add(0, e); }
/**
* 在链表末尾添加一个新元素e
*/
public void addLast(E e) { add(size, e); }
链表添加节点.png
2.3.改和查的方法
/**
* 获取链表的第index(0-based)位置的元素e
* @param index ：获取链表元素的索引位置
* @return ：该索引的元素
*/
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
//从头元素(头结点)开始
Node cur = dummyHead.next;
//获取第index位置结点
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
/**
* 获取链表中第一个元素(头节点元素)
* @return ：dummyHead.next.e;
*/
public E getFirst() { return get(0); }
/**
* 获取链表中最后一个位置的元素
* @return ：
*/
public E getLast() { return get(size - 1); }
/**
* 修改链表中第index(0-based)位置的元素
* 在链表中不是一个常用的操作，练习用
*/
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
//从头元素(头结点)开始
Node cur = dummyHead.next;
//获取第index位置结点
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
/**
* 该链表中是否存在该元素
* @param e ：
* @return ：
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
2.4.删除方法
/**
* 删除链表中index(0-based)位置的元素，并返回该元素：将删除节点的next结点代替成删除节点的位置
* @param index ：删除节点的索引
* @return ：删除节点的元素
*/
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed. Illegal index");
}
//从虚拟头节点开始
Node prev = dummyHead;
//获取第index位置结点的上一个结点（前结点）
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node deleteNode = prev.next;
prev.next = deleteNode.next;
deleteNode.next = null;
size--;
return deleteNode.e;
}
/**
* 删除链表中第一个元素，并返回元素值
* @return ：
*/
public E removeFirst() { return remove(0); }
/**
* 删除结点中最后一个元素，并返回元素值
* @return ：
*/
public E removeLast() { return remove(size - 1); }
2.5.重写toString方法
@Override
public String toString() {
StringBuilder str = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
str.append(cur + "-->");
cur = cur.next;
}
str.append("NULL");
return str.toString();
}
