public class LinkedList<E> {
private Node<E> first;//第一个节点
private Node<E> last;//最后一个节点
private int size = 0; //节点总个数记录
/**
* 向每个列表的尾部追加元素（尾插法）
*
* 心得：一个结点保存了当前的数据，还有下个结点的信息，下个结点保存了下下个结点的信息，所以
* 只需要知道头结点那么就可以一个一个的找下去。
*
* 在理解尾结点这个概念的时候，不要过多的纠结。可以把他理解成保存了最后一个结点地址的结点，我们在插入的
* 时候就很容易，因为我们已经最后一个结点的位置，那么只需要在最后一个结点的下一个结点插入当前当前结点
* 信息。 last = node；这个方法就又一次的记录最后一个结点的地址。
* @param data
* @return
*/
public boolean add(E data) {
Node<E> node = new Node<E>(data, null);
/**
* 我们采用的是头结点制空的方式插入的，如果头结点的下一个结点为空，那么是第一次插入
* 把结点插入，尾结点指向第一个元素
*/
if (first.next == null) {
first.next = node;
last = node;
} else {
/**
* 如果是第二次插入，因为我们已经知道尾结点的地址，那么直接在尾结点的next插入。
* 然后尾结点下标指向新插入的结点位置。以此类推。
*/
last.next = node;
last = node;
}
size++;
return true;
}
public E get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}
Node<E> x = first.next;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x.data;
}
public void set(int index, E data) {
if (index < 0) {
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}
if (index >= size) {
add(data);
} else {
int count = 0;
Node<E> x = first;
while (x.next != null) {
if (count++ == index) {
x.next = new Node<>(data, x.next);
size ++;
return ;
}
x = x.next;
}
}
}
/**
* 头插法
* @param data
* @return
*/
public boolean addFirst(E data) {
Node<E> node = new Node<E>(data, first.next);
first.next = node;
size++;
return true;
}
/**
* 删除指定位置的元素
* @param index
* @return
*/
public boolean remove(int index) {
if (size < 1 || index < 0 || index >= size() ) {
return false;
}
Node<E> node = first;
int count = 0;
while (node.next != null) {
/**
* 这地方我们是用下一个节点和要删除的元素进行比较的
* 如果下一个节点的data等于要删除元素
* 那么就把下一节点的next()域添加到当前位置
*/
if (count++ == index) {
node.next = node.next.next;
size --;
return true;
}
node = node.next;
}
return false;
}
public int size() {
return size;
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("[ ");
Node<E> node = first;
while (node.next != null) {
sb.append(node.next.data + " ,");
node = node.next;
}
sb.append(" ]");
return sb.toString();
}
public LinkedList() {
super();
// 头结点制空
first = new Node<>();
}
//Node
private static class Node<E> {
E data;
Node<E> next; //下一个节点
public Node(E data, Node<E> next) {
super();
this.data = data;
this.next = next;
}
public Node() {
}
}
}
