JDK源码阅读——-自学笔记(二十四)(java.util.LinkedList 再探 自定义讲解)
一、实现get方法
1、一般思维实现思路
- 1)、将对象的值放入一个中间变量中。
- 2)、遍历索引值，将中间量的下一个元素赋值给中间量。
- 3)、返回中间量中的元素值。
- 4)、示意图
- get(2),传入角标,循环两次获取到[1]元素,如图.
2、实现思路实现
/**
* 最基本的写法
*
* <p>按照角标循环元素,获取最后一个元素的值</p>
*
* <p>存在问题:效率不高</p>
*
* @param index 元素的角标
* @return 角标代表的元素
*/
public Object get(int index) {
Node node = firstNode;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.elements;
}
/**
* @author liuyangos8888
*/
public class TestGet {
public static void main(String[] args) {
testGetBase();
}
private static void testGetBase() {
MyGetLinkedList001 myGetLinkedList001 = new MyGetLinkedList001();
myGetLinkedList001.add("A");
myGetLinkedList001.add("B");
myGetLinkedList001.add("C");
myGetLinkedList001.add("D");
myGetLinkedList001.add("E");
myGetLinkedList001.add("F");
System.out.println(myGetLinkedList001.get(4));
}
}
3、思路缺少的条件
// 判断索引范围
if (index < 0 || index > size - 1) {
throw new RuntimeException("索引不合法!" + index);
}
- 2)、查找方式的优化问题(获取第888个索引时候,效率极低,建议使用折半查找)
/**
* 优化版,提高查找效率,折半判断
*
* @param index 索引角标
* @return 索引对应的值
*/
public Object get1(int index) {
// 判断索引范围
if (index < 0 || index > size - 1) {
throw new RuntimeException("索引不合法!" + index);
}
Node node = null;
// size>>1 除以2
if (index <= (size >> 1)) {
node = firstNode;
for (int i = 0; i < index; i++) {
node = node.next;
}
} else {
node = lastNode;
for (int i = size - 1; i > index; i--) {
node = node.previous;
}
}
return node.elements;
}
- 3)、发现的其他问题(采用此方式get时候,add需要size++)
// 不做size++,在get判断范围的时候就会出现错误
public void add(Object o) {
Node node = new Node(o);
if (firstNode == null) {
firstNode = node;
} else {
node.previous = lastNode;
node.next = null;
lastNode.next = node;
}
lastNode = node;
size++;
}
二、实现remove方法
1、一般思维实现思路
- 1)、把前一个元素的next元素，变为next.next元素
- 2)、把最后一个元素的previous元素，变为previous.previous元素
- 3)、size值减少操作
- 4)、示意图
- 有A、B、C三个节点，以链表形式存储（如上图）
- 现在要删除节点B，A、C不变（如上图）
- 方法就是截断A、C跟B的连接，A和C重新建立新的连接，JAVA的实现方式就是，用对象覆盖B节点的值。
2、实现思路实现
/**
* 根据索引,删除数组中元素
*
* @param index 索引角标
*/
public void remove(int index) {
Node temp = getNode(index);
if (temp != null) {
Node up = temp.previous;
Node down = temp.next;
if (up != null) {
up.next = down;
}
if (down != null) {
down.previous = up;
}
size--;
}
}
/**
* @author liuyangos8888
*/
public class TestRemove {
public static void main(String[] args) {
MyGetLinkedList002 myGetLinkedList002 = new MyGetLinkedList002();
myGetLinkedList002.add("A");
myGetLinkedList002.add("B");
myGetLinkedList002.add("C");
myGetLinkedList002.add("D");
myGetLinkedList002.add("E");
myGetLinkedList002.add("F");
System.out.println(myGetLinkedList002);
myGetLinkedList002.remove(3);
System.out.println(myGetLinkedList002);
myGetLinkedList002.remove(0);
System.out.println(myGetLinkedList002);
myGetLinkedList002.remove(3);
System.out.println(myGetLinkedList002);
}
}
3、思路缺少的条件
// 判断索引范围
if (index < 0 || index > size - 1) {
throw new RuntimeException("索引不合法!" + index);
}
// 删除第一个元素的时候
if (index == 0) {
firstNode = down;
}
// 删除最后一个元素的时候
if (index == size - 1) {
lastNode = up;
}
三、实现insert(add)方法
1、一般思维实现思路
- 1)、获取索引的元素值,得到元素的前一个节点
- 2)、把前节点的后一个节点设置为加入的节点
- 3)、新节点的前一个节点设置为索引值节点的前节点
- 4)、前一个节点的后一个节点是索引值节点
- 5)、索引值节点的前一个节点是新节点
- 6)、示意图
- 有A、B、C三个节点，以链表形式存储,现在要添加D节点,到链表中.
- 切断A、B的节点连接，A和D，D和B重新建立连接，生成新的链表
2、实现思路实现
/**
* 插入一个元素在指定位置
*
* @param index 指定位置索引
* @param o 插入的元素
*/
public void insert(int index, Object o) {
Node newNode = new Node(o);
// 判断范围
checkRound(index);
Node temp = getNode(index);
if (temp != null) {
// 第一个元素和最后一个元素的时候
if (index == 0 || index == size - 1) {
temp.elements = newNode.elements;
} else {
Node up = temp.previous;
isNull(up == null, "前一个元素为空");
up.next = newNode;
newNode.previous = up;
newNode.next = temp;
temp.previous = newNode;
}
}
}
/**
* 插入一个元素在指定位置
*
* @param index 指定位置索引
* @param o 插入的元素
*/
public void insert1(int index, Object o) {
Node newNode = new Node(o);
// 判断范围
checkRound(index);
Node temp = getNode(index);
if (temp != null) {
// 第一个元素和最后一个元素的时候
if (index == 0) {
firstNode = newNode;
newNode.next = temp.next;
} else if (index == size - 1) {
Node up = temp.previous;
isNull(up == null, "前一个元素为空");
up.next = newNode;
newNode.previous = up;
} else {
Node up = temp.previous;
isNull(up == null, "前一个元素为空");
up.next = newNode;
newNode.previous = up;
newNode.next = temp;
temp.previous = newNode;
}
}
}
public class TestInsert {
public static void main(String[] args) {
MyInsertLinkedList003 myInsertLinkedList003 = new MyInsertLinkedList003();
myInsertLinkedList003.add("A");
myInsertLinkedList003.add("B");
myInsertLinkedList003.add("C");
myInsertLinkedList003.add("D");
myInsertLinkedList003.add("E");
myInsertLinkedList003.add("F");
myInsertLinkedList003.insert1(1,"G");
System.out.println(myInsertLinkedList003);
}
}
3、思路缺少的条件
private void checkRound(int index) {
// 判断索引范围
isNull(index < 0 || index > size - 1, "索引不合法!" + index);
}
/**
* 判断空指针问题
*
* @param b 判断条件
* @param string 抛出异常的原因
*/
private void isNull(boolean b, String string) {
if (b) {
throw new RuntimeException(string);
}
}
if (temp != null) {
// 第一个元素和最后一个元素的时候
if (index == 0) {
firstNode = newNode;
newNode.next = temp.next;
} else if (index == size - 1) {
Node up = temp.previous;
isNull(up == null, "前一个元素为空");
up.next = newNode;
newNode.previous = up;
} else {
Node up = temp.previous;
isNull(up == null, "前一个元素为空");
up.next = newNode;
newNode.previous = up;
newNode.next = temp;
temp.previous = newNode;
}
}
四、实现泛型和全部代码
package com.synway.test.collections.version3.finallist;
import com.synway.test.collections.version3.basesimple.Node;
/**
* 最终手写版,添加泛型
*
* @author liuyangos8888
*/
public class MyLinkedListFinal<T> {
/**
* 第一个节点
*/
private Node firstNode;
/**
* 最后一个节点
*/
private Node lastNode;
/**
* 链表大小
*/
private int size;
/**
* 添加节点到数组中
*
* @param o 节点数据
*/
public void add(T o) {
Node node = new Node(o);
if (firstNode == null) {
firstNode = node;
} else {
node.previous = lastNode;
node.next = null;
lastNode.next = node;
}
lastNode = node;
size++;
}
/**
* 根据索引,删除数组中元素
*
* @param index 索引角标
*/
public void remove(int index) {
checkRound(index);
Node temp = getNode(index);
if (temp != null) {
Node up = temp.previous;
Node down = temp.next;
if (up != null) {
up.next = down;
}
if (down != null) {
down.previous = up;
}
// 删除第一个元素的时候
if (index == 0) {
firstNode = down;
}
// 删除最后一个元素的时候
if (index == size - 1) {
lastNode = up;
}
size--;
}
}
/**
* 插入一个元素在指定位置
*
* @param index 指定位置索引
* @param o 插入的元素
*/
public void insert(int index, T o) {
Node newNode = new Node(o);
// 判断范围
checkRound(index);
Node temp = getNode(index);
if (temp != null) {
// 第一个元素和最后一个元素的时候
if (index == 0) {
firstNode = newNode;
newNode.next = temp.next;
} else if (index == size - 1) {
Node up = temp.previous;
isNull(up == null, "前一个元素为空");
up.next = newNode;
newNode.previous = up;
} else {
Node up = temp.previous;
isNull(up == null, "前一个元素为空");
up.next = newNode;
newNode.previous = up;
newNode.next = temp;
temp.previous = newNode;
}
}
}
/**
* 优化版,提高查找效率,折半判断
*
* @param index 索引角标
* @return 索引对应的值
*/
public T get(int index) {
checkRound(index);
Node node = getNode(index);
return node != null ? (T) node.elements : null;
}
/**
* 根据角标,获取节点
*
* @param index 传入角标
* @return 获取节点
*/
private Node getNode(int index) {
Node node;
// size>>1 除以2
if (index <= (size >> 1)) {
node = firstNode;
for (int i = 0; i < index; i++) {
node = node.next;
}
} else {
node = lastNode;
for (int i = size - 1; i > index; i--) {
node = node.previous;
}
}
return node;
}
/**
* 审核传入的角标范围是否越界
*
* @param index 传入角标
*/
private void checkRound(int index) {
// 判断索引范围
isNull(index < 0 || index > size - 1, "索引不合法!" + index);
}
/**
* 判断空指针问题
*
* @param b 判断条件
* @param string 抛出异常的原因
*/
private void isNull(boolean b, String string) {
if (b) {
throw new RuntimeException(string);
}
}
/**
* 获取数组中元素
*
* @return 元素数组
*/
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
Node temp = firstNode;
while (temp != null) {
stringBuilder.append(temp.elements).append(",");
temp = temp.next;
}
stringBuilder.setCharAt(stringBuilder.length() - 1, ']');
return stringBuilder.toString();
}
}
