上面学习了单链表，现在我们用单链表实现LinkedList。
实现LinkedList主要就是实现增删改查这几个操作。我们直接看代码，代码里面注释写的很详细，就不再过多说明。
/**
* 用单链表实现LinkedList
*/
public class MyLinkedList<T> {
private int size;
//链表头节点
private Node head;
public MyLinkedList() {
size = 0;
}
/**
* 增加数据
*
* @param data
*/
public void add(T data) {
Node headLast = head;
Node curNode = new Node(data, headLast);
head = curNode;
size++;
}
/**
* 在指定位置增加数据
*
* @param index
* @param data
*/
public void add(int index, T data) {
//检查是否越界
checkIndexOutOfBounds(index);
Node preNode = head;
Node currentNode = head;
for (int i = 0; i < index; i++) {
//把当前节点赋值给前一个节点
preNode = currentNode;
//下一个节点赋值给当前节点，这样就可以实现向下轮循
//当i=index-1时，preNode就指向要插入位置的前一个节点，currentNode就是要插入位置的节点
currentNode = currentNode.next;
}
//创建新阶段，要插入位置的节点作为新节点的下一个节点next
Node nodeNew = new Node(data, currentNode);
//将新节点赋值给要插入位置的前一个节点的next
preNode.next = nodeNew;
size++;
}
/**
* 删除链表表头的数据
*
* @return 被删除的数据
*/
public T remove() {
if (head == null) {
return null;
}
Node headLast = head;
Node next = headLast.next;
//next赋值给头节点
head = next;
//将原来的头节点的next设置为null,使原来的头节点不再持有其他节点的引用，
// 使GC可以回收，以防止内存泄漏
headLast.next = null;
size--;
return headLast.data;
}
/**
* 删除指定位置的节点
*
* @param index
* @return
*/
public T remove(int index) {
//检查是否越界
checkIndexOutOfBounds(index);
Node preNode = head;
Node currentNode = head;
for (int i = 0; i < index; i++) {
preNode = currentNode;
currentNode = currentNode.next;
}
//将前一个节点的next指向要删除节点的下一个节点
preNode.next = currentNode.next;
//将要删除的节点的next设置为null,使原来的头节点不再持有其他节点的引用，
// 使GC可以回收，以防止内存泄漏
currentNode.next = null;
size--;
return currentNode.data;
}
/**
* 删除链表尾部的数据
*
* @return
*/
public T removeLast() {
if (head == null) {
return null;
}
Node preNode = head;
Node currentNode = head;
while (currentNode.next != null) {
preNode = currentNode;
currentNode = currentNode.next;
}
//将倒数第二个节点的next设置为空，即将倒数第二个节点设置为最后一个节点
preNode.next = null;
size--;
return currentNode.data;
}
/**
* 改变某个节点的数据
*
* @param index
* @param dataNew
*/
public void set(int index, T dataNew) {
//检查是否越界
checkIndexOutOfBounds(index);
Node currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode.next;
}
currentNode.data = dataNew;
}
/**
* 获取链表表头的数据
*
* @return
*/
public T get() {
if (head == null) {
return null;
}
return head.data;
}
/**
* 获取某个位置的数据
*
* @param index
* @return
*/
public T get(int index) {
//检查是否越界
checkIndexOutOfBounds(index);
Node currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode.data;
}
/**
* 单链表的节点类
* 节点存储自己的data数据+下一个节点Next
*/
class Node {
T data;
Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
/**
* 检查是否越界
*
* @param index
*/
public void checkIndexOutOfBounds(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("indexL " + index + " size: " + size);
}
}
@Override
public String toString() {
Node currentNode = head;
for (int i = 0; i < size; i++) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.next;
}
System.out.println();
return super.toString();
}
}
测试代码
public static void main(String[]args){
MyLinkedList<Integer> list = new MyLinkedList<>();
for(int i = 0; i < 5; i++) {
list.add(i);
}
list.toString();
list.add(3,3);
list.toString();
list.add(8);
list.toString();
System.out.println(list.get(2));
}
输出：
4 3 2 1 0
4 3 2 3 1 0
8 4 3 2 3 1 0
3
网友评论