通过阅读LinkedList的api, 自己用代码实现他的常用方法;
import java.util.List;
public class MyLinkedList {
//链表的首地址
private Node first = null;
//尾节点
private Node last = null;
//记录链表的有效长度
private int size = 0;
//往链表中添加元素 (在尾部)
public boolean add(Object o) {
this.addLast(o);
return true;
}
//在此列表中指定的位置插入指定的元素
public void add(int index,Object element) {
//index越界判断
if (index < 0 || index > size) {
return;
}
//创建新节点
Node node = new Node();
node.data = element;
node.next = null;
//链表为空
if (this.last == null) {
this.first = node;
this.last = node;
}else {
//链表不为空
//开头添加
if (index == 0) {
this.addFirst(element);
}else if (index == size) {
//尾部添加
this.addLast(element);
}else {
//中间添加
Node preNode = this.node(index - 1);
//开始preNode的next指的是indexNode
Node indexNode = preNode.next;
node.next = indexNode;
preNode.next = node;
this.size++;
}
}
}
//根据下标找节点
private Node node(int index) {
//判断index
if (index < 0 || index >= size) {
return null;
}
//设置一个循环标记
int tag = 0;
//先给一个空节点
Node temp = null;
for (Node l = first; l != null; l = l.next) {
//找到下标
if (tag == index) {
//将l赋给temp
temp = l;
break;
}
tag++;
}
return temp;
}
//根据下标找元素
public Object get(int index) {
//判断index
if (index < 0 || index >= size) {
return null;
}
//根据下标找到节点的元素
//调用node方法
return this.node(index).data;
}
//在头部添加 (将指定元素插入到此列表的头部)
public void addFirst(Object o) {
//创建新节点
Node node = new Node();
node.data = o;
node.next = null; // 不写默认就是空
if (this.last == null) { //链表为空
//链表中一个元素都没有.直接将新的节点设置成头节点,头节点和尾节点是一样的
this.first = node;
this.last = node;
}else { //链表不为空
//链表中有元素
//让新节点的地址指向原来的first,这样就变成头节点了
node.next = first;
//然后把新的节点设置成头节点
this.first = node;
}
this.size++;
}
//在尾部添加 (将指定元素插入到此列表的尾部)
public void addLast(Object o) {
Node node = new Node();
node.data = o;
node.next = null;
//一个元素都没有
if (this.last == null) {
this.first = node;
this.last = node;
}else {
//有元素
this.last.next = node;
this.last = node;
}
this.size++;
}
//返回链表的长度
public int size() {
return this.size;
}
//构造方法
public MyLinkedList() {
}
//构造一个包含指定List中的元素的列表
public MyLinkedList(List list) {
}
//循环
@Override
public String toString() {
String string = "[";
//链表的遍历
for (Node l = first; l != null; l = l.next) {
Object object = l.data;
string = string + object.toString();
string = string + ",";
}
if (string.length() >= 2) {
//裁剪字符串,从0号元素到他的长度减一个位置,不要最后的逗号
string = string.substring(0, string.length() - 1);
}
string += "]";
return string;
}
//修改元素
public Object set(int index,Object element) {
//判断index的范围
if (index < 0 || index >= size) {
return null;
}
//根据index查找节点
Node node = this.node(index);
//记录原来的值
Object temp = node.data;
//修改元素
node.data = element;
return temp; //返回修改前的记录
}
//删除节点 (根据下标移除节点)
public Object remove(int index) {
if (index < 0 || index >= size) {
return null;
}
Node temp = null; //定义临时变量接收要删除的值
//只有一个节点的时候
if (this.size == 1) {
temp = this.first; //记录要删除的节点
this.first = null;
this.last = null;
}//两个节点及以上,且不是删除首节点
else if(index != 0) {
//根据下标找到节点(如果有多个元素)
//比如有三个节点,我们要删除第二个,先找到第一个,然后将第一个节点的地址设置成要删除的节点的地址
Node preNode = this.node(index - 1);
//preNode.next指向的是他后边的节点,赋给node
Node node = preNode.next;
temp = node; //记录要删除的节点
preNode.next = node.next;
}else { //两个节点及以上,且删除首节点
temp = this.first; //记录要删除的节点
//如果删除第一个元素;将第一个元素指向的地址设置成首地址就可以
this.first = this.first.next;
}
this.size--;
return temp.data; //返回要删除的元素
}
//是否包含某元素
public boolean contain(Object o) {
return indexOf(o) != -1;
}
//根据元素返回下标
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node l = first; l != null; l = l.next) {
if (l.data == null) {
return index;
}
index++;
}
}else {
for (Node l = first; l != null; l = l.next) {
if (o.equals(l.data)) {
return index;
}
index++;
}
}
return -1; //找不到元素
}
}
//节点
class Node {
Object data; //存数据
Node next; //下个节点的引用 类似于: (Person p = new Person();)
}
