一. 简单总结
- LinkedList底层实现方式是
双向链表 - 链表的优缺点（当然是和数组比较而言）
- 单链表的优缺点
- 优点：增加，删除某一个元素快
- 缺点：查询慢，自然修改某个元素的值也慢了（修改的前提是先要找到这个节点）- 单链表使用场景举例：
MessageQueue（每次只能添加一个message，而且不能从尾节点访问，所以只能使用单链表,因此Message就是这里的Node了，因此Message类里面一定有一个next指针）
- 单链表使用场景举例：
- 双链表针对单链表查询慢的缺点，通过增加指针来通过
折半查找提高查询效率，典型的通过空间换时间的做法。
- 单链表的优缺点
3.注意事项：
- 在用
java实现链表这种数据结构时，一定要严格区分对对象的引用与对象之间的区别，即在Object object=new Object();中，另一个对象指向左边的object和指向右边的new Object()是完全不一样的。
二. 单链表增删实现
- 添加一个节点
构造节点- 特别注意：这二个成员变量是必须的，但在具体的使用场景中，还会有其他成员变量，而且不一定是 T data这种形式，也不一定叫
Node，比如MessageQueue里面装的Message就是这里的Node，所以不要执迷于名字、表象，而在于刻画出的数据模型和本质，这才是数据结构要研究的东西
- 特别注意：这二个成员变量是必须的，但在具体的使用场景中，还会有其他成员变量，而且不一定是 T data这种形式，也不一定叫
class Node<T>{
T data;//我们要存储的数据
Node<T> next;//指向下一个节点的引用（指针）
}
增加一个节点
//这二步的顺序一定不能错
s.next=p.next;//第一步，将a[i+1]的地址赋值给s的指针域
p.next=s;//第二步，将s的地址复制给a[i]的指针域
-
删除一个节点
删除一个节点
p.next=p.next.next;
三. 双链表增删实现
-
添加一个节点
情形一：
增加一个节点
s.prior=p; //第一步，将p节点的地址赋值给s的前驱
s.next=p.next; //第二步，将p.next的节点的地址赋值给s的后继
p.next.prior=s; //第三步，将的s的地址赋值给p.next节点的前驱
p.next=s; //第四步，将s的地址赋值给p节点的后继
情形二：
增加一个节点
s.prior=p.prior; //第一步
s.next=p; //第二步
p.prior.next=s; //第三步
p.prior=s; //第四步
注意到：情形一和情形二的第三步和第四步的顺序刚好的相反的，而且这两步的顺序一定不能错。
这四步之间有严格的前后关系,不能轻易替换，当然还有另一种顺序，这里是实际开发中用的最多的写法，但思想都是一样的，这里的思路是
（1） 先将新节点s的前驱和后继填满（即赋值），这就是第一第二步；
（2） 再将s的地址分别赋值给p以及p.next节点，这就是第三第四步；
- 特别注意：
在添加一个节点的时候， 第一第二步一般是最先做的，这个前后顺序可以变，但是第三第四步的顺序一定不能变
-
删除一个节点
删除一个节点
p.prior.next=p.next; //第一步
p.next.prior=p.prior; //第二步
四. LinkedList源码手写实现（主要写增删改查操作）
/**
* linkedList底层实现方式：双链单循环表
* 对linkedList实现增删改查操作
*/
public class LinkedList<E> {
/**
* 对于LinkedList来说,三个重要的参数：这三个重要参数就是LinkedList的属性--->成员变量
* 第一个:头节点
* 第二个:尾节点
* 其实，只要有一个头节点就可以拿到LinkedList的所有元素了，
* 但是因为是双链表，可以通过尾节点利用二分查找提高效率,典型的用空间换时间
*
* 第三个:长度
* 这个属性是给调用者使用的，对LinkedList内部来说意义并不大
*/
//头节点
private Node<E> first;
//尾节点
private Node<E> last;
//长度
private int size;
//空参构造方法
public LinkedList() {
}
//如果传进来的是一个集合，就相当于把集合中的每个元素加入到LinkedList中
public LinkedList(Collection<? extends E>/*E或者E的子类*/ c) {
addAll(c);
}
/**
* 添加集合
*
* @param c 要添加的集合
*/
private boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 在指定位置添加集合
*
* @param index 指定位置
* @param c 要添加的集合
*/
private boolean addAll(int index, Collection<? extends E> c) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
//先将其转换成数组，然后再一个个连起来
Object[] a = c.toArray();
int s = a.length;
if (s == 0) {//表明集合的长度为0，没有什么要添加的
return false;
}
Node<E> front, rear;
//在最后的位置添加一个节点
Node<E> pred, succ;
//边界检测
if (index == size) {
//如果插入位置是size,则在头节点前面插入，否则在获取index处的节点插入
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.pre;
}
//将这些节点连起来
for (Object o : a) {
@SuppressWarnings("unchecked")
E e = (E) o;
Node<E> newNode = new Node<>(pred, null, e);
if (pred == null) {
first = newNode;
} else {
pred.next = newNode;
}
pred = newNode;
//收尾处理
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.pre = pred;
}
}
size += s;
return true;
}
/**
* 添加一个元素
*
* @param e
* @return
*/
public boolean add(E e) {
//添加一个元素相当于在链表的尾部加入一个元素
linkLast(e);
return true;
}
/**
* 在index的位置添加一个节点
*
* @param index 指定位置
* @param e 要添加的值
* @return 是否添加成功
*/
public boolean add(int index, E e) {
if (index < 0 || index > size) {
return false;
}
//插入的位置刚好是尾节点，实际上size的位置是没有节点的，就相当于在尾部新添加一个元素
if (index == size) {
linkLast(e);
} else {
//在任意位置新添加一个节点，首先拿到index位置的节点，
// 在这个节点之前插入一个元素，然后所有的节点“后移”一个位置
//因此还需要得到index位置之前的节点
//1.目标位置
Node<E> target = node(index);
//2.获取index前面的节点
Node<E> prev = target.pre;
//3.构造新的节点
//4.将新的节点添加到index的位置
//添加的第一第二步
Node<E> newNode = new Node<>(prev, target, e);
//第三步
if (prev == null) {
//表明target就是头节点，相当于在头节点前面在添加一个节点
first = newNode;
} else {
prev.next = newNode;
}
//第四步
// prev = newNode;//这种写法是错的，
// 在java里面一定要弄清楚 `对对象的引用` 与 `对象` 之间的区别
target.pre = newNode;
//5.长度增加
size++;
}
return true;
}
public E remove(int index) {
if (index < 0 || index > size) {
throw new NoSuchElementException();
}
Node<E> target = node(index);
return unlinkNode(target);
}
private E unlinkNode(Node<E> p) {
// p.pre.next = p.next;
// p.next.pre = p.pre;
Node<E> prev = p.pre;
Node<E> next = p.next;
if (prev == null) {
//等价于删除头节点
first = p.next;
} else {
prev.next = p.next;
}
if (next == null) {
//等价于删除尾节点
last = p.pre;
} else {
next.pre = p.pre;
}
return p.data;
}
/**
* 获取指定位置的元素
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index >= size) {
return null;
}
return node(index).data;
}
private static final String TAG = "LinkedList";
/**
* 获取指定位置的节点
* @param index
* @return
*/
private Node<E> node(int index) {
//表明位于链表的前半部分
if (index < (size >> 1)) {
//如果位于链表的前半部分，则从头节点开始查找
Node<E> node = first;
//这里index代表要循环的次数，即从first节点开始往下找，需要找几次才能找到，
// 因为从前往后数，first的index永远等于0
//同理从后向前数，last的index永远为0
//index表示指定位置的节点和头节点之间有几个节点，有几个节点就要通过指针向下找几次
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
//从后往前查找
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.pre;
}
return node;
}
}
private void linkLast(E e) {
Node<E> l = last;
Node<E> newNode = new Node<>(l, null, e);
//如果最后一个节点为空，表明是一个空链，当前添加的元素是第一个元素
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
last = newNode;
size++;
}
public int size() {
return size;
}
//构造一个节点node，这个node是linkedList的数据单元
private static class Node<E> {
private Node<E> pre;//前驱
private Node<E> next;//后继
private E data;
public Node(Node<E> pre, Node<E> next, E e) {
this.pre = pre;
this.next = next;
this.data = e;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
}
网友评论