一、实现get方法 1、一般思维实现思路
1)、将对象的值放入一个中间变量中。
2)、遍历索引值，将中间量的下一个元素赋值给中间量。
3)、返回中间量中的元素值。
4)、示意图
get(2),传入角标,循环两次获取到[1]元素,如图.
2、实现思路实现1)、核心方法
/** * 最基本的写法 * * <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; }2)、测试
/** * @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、思路缺少的条件1)、判断索引范围问题
// 判断索引范围 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、实现思路实现1)、核心方法
/** * 根据索引,删除数组中元素 * * @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--; } }2)、测试
/** * @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、思路缺少的条件1)、判断索引范围问题
// 判断索引范围 if (index < 0 || index > size - 1) { throw new RuntimeException("索引不合法!" + index); }2)、第一个元素删除和最后一个元素删除问题
// 删除第一个元素的时候 if (index == 0) { firstNode = down; } // 删除最后一个元素的时候 if (index == size - 1) { lastNode = up; } 三、实现insert(add)方法 1、一般思维实现思路1)、获取索引的元素值,得到元素的前一个节点
2)、把前节点的后一个节点设置为加入的节点
3)、新节点的前一个节点设置为索引值节点的前节点
4)、前一个节点的后一个节点是索引值节点
5)、索引值节点的前一个节点是新节点