------------ 本文来自 阿P官方博客
一、什么是链表
- 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。而本次实现类的Node就是指针的另一种形式。
- 几种链表的表现形式(如下图所示:图片来源自网络，侵删)
image
二、链表的特点
- 链表不用考虑存储的长度，可充分利用内存空间，灵活管理。
- 从首尾查找元素快：queue的基本实现
- 双向链表：底层以结点(Node)形式存储数据。
- 增删容易，查找中间的数据比较难。【注意这里的增删只是增删结点的容易度，实 际上是先查找到某个结点，再进行增删】
- 线程不安全
三、实现过程
- 主类属性：
- first：首位Node对象
- end：末位Node对象
- size：数据大小
- Node属性：
- prev：前一位Node对象或null（首位为null）
- next：后一位Node对象或null（末位为null）
- item：实际存储数据
- 存储过程
- 每一个Node都是一个Java对象，存储在堆内存空间中，并且此空间任意(区分 于数组的堆内存空间必须连续的特性)。
- 图解(如下图1所示)
image
四、实现方法
- 新增元素：add(T o)
- 插入元素：add(int index, T o)
- 设置元素：set(int index, T o)
- 获取元素：T get(int index)
- 获取首次存入的index：int indexOf(T o)
- 获取末次存入的index：int lastIndexOf(T o)
- 根据位置删除元素：T remove(int index)
- 根据值删除元素：T remove(T o)
五、实现代码
package cn.wxqsearch.ListDemo;
public class MyLinkedList<T> {
//元素个数、结点个数
public int size;
//头结点和尾结点
private Node<T> first = null;
private Node<T> end = null;
public MyLinkedList() {
super();
size=0;
}
/**
* 添加
* @param o
*/
public void add(T o) {
if (first == null || end == null) {
Node<T> node = new Node<T>(o, null, null);
end=node;
first = node;
} else {
Node<T> node = new Node<T>(o, end, null);
end.next = node;//原最后一个元素的尾 = 当前node
end=node;//新最后的元素 = 当前
}
size ++;
}
/**
* 按位置插入
* @param index
* @param o
*/
public void add(int index, T o) {
//1.从尾巴插入
if (index == size) {
add(o);
return;
}
//2.从头部插入
if (index == 0) {
Node<T> node = new Node<T>(o, null, null);
this.first.prev = node;
first = node;
return;
}
//3.从中间插入
addIn(index, o);
size++;
}
/**
* 获取node
* @param index
* @return
*/
public T get(int index) {
return getNode(index).item;
}
/**
* 获取元素首次出现位置
* @param t
* @return
*/
public int indexOf(T t) {
Node<T> node = first;
for (int i = 0; i < size; i++) {
if (t.equals(node.item)) {
return i;
}
node = node.next;
}
return -1;
}
/**
* 获取元素最后一次的位置
* @param t
* @return
*/
public int lastIndexOf(T t) {
Node<T> node = end;
for (int i = size-1; i >= 0; i--) {
if (t.equals(node.item)) {
return i;
}
node = node.prev;
}
return -1;
}
/**
* 设置某一位的值
* @param index
* @param t
*/
public void set(int index, T t) {
getNode(index).item = t;
}
/**
* 移除某位的值
* @param index
* @return
*/
public T remove(int index) {
T item;
//越界情况
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
//只有1个元素
if (size == 1) {
item = first.item;
end = null;
first = null;
return item;
}
//首位
if (index == 0) {
item = first.item;
first.next.prev = null;
return item;
}
//尾位
if (index == size-1) {
item = end.item;
end.prev.next = null;
return item;
}
//中间位
Node<T> node = getNode(index);
Node<T> prev = node.prev;
Node<T> next = node.next;
prev.next = next;
next.prev = prev;
return node.item;
}
public T remove(T o) {
return remove(indexOf(o));
}
//从中间插入
private void addIn(int index, T o) {
Node<T> node = getNode(index);//获取某个下标的node
Node<T> node1 = new Node<T>(o, node.prev, node.next);
//前一位的next = 当前
node.prev.next = node1;
//自己的prev = 当前
node.prev=node1;
}
/**
* 获取指定下标结点
* @param index
* @return
*/
private Node<T> getNode(int index) {
if (index == 0) {
return first;
}
if (index == size-1) {
return end;
}
Node<T> node;
if (index < (size >>1)) {
//从头
node = first.next;//第二个
for (int i = 0; i <= (size >>1); i++) {
if (i == index-1) {
break;
}
node = node.next;
}
} else {
//从尾
node = end.prev;//第二个
for (int i = 0; i <= (size >>1); i++) {
if (i == size-index-2) {
break;
}
node = node.next;
}
}
return node;
}
/**
* 结点类：记录存储的头键、尾键、数据。
* @param <T>
*/
private class Node<T> {
private T item;
private Node<T> prev;
private Node<T> next;
public Node(T item, Node<T> prev, Node<T> next) {
super();
this.item = item;
this.prev = prev;
this.next = next;
}
}
@Override
public String toString() {
Node node = first;
StringBuilder str = new StringBuilder("["+node.item);
for (int i = 0; i < size-1; i++) {
node = node.next;
str.append("," + node.item);
}
str.append("]");
return str.toString();
}
}
