028_自己实现一个LinkedList

/*** 自定义链表*/ public class MyLinkedList {private Node first;private Node last;private int size;/*** 构造方法*/public MyLinkedList() {}/*** 链表大小* @return*/public int size() {return size;}/*** 数组是否为空* @return*/public boolean isEmpty() {return size == 0;}/*** 检测下标是否越界* @param index*/private void checkElementIndex(int index) {if(!(index >= 0 && index < size)) {throw new IndexOutOfBoundsException();}}/*** 插入元素位置是否合法* @param index* @return*/private void checkPositionIndex(int index) {if(!(index >= 0 && index <= size)) {throw new IndexOutOfBoundsException();}}/*** 往链表结尾插入元素* @param o*/private void linkLast(Object o) {Node temp = last;Node newNode = new Node(temp, o, null);last = newNode;if(temp == null) {first = newNode;}else {temp.next = newNode;}size++;}/*** 往某个节点之前插入元素* @param o* @param x*/private void linkBefore(Object o, Node x) {Node pre = x.prev;Node newNode = new Node(pre, o, x);x.prev = newNode;if(pre == null) {first = newNode;}else {pre.next = newNode;}size++;}/*** 添加元素* @param o* @return*/public boolean add(Object o) {linkLast(o);return true;}/*** * @param index* @param o* @return*/public void add(int index, Object o) {checkPositionIndex(index);if(index == size) {linkLast(o);}else {linkBefore(o, node(index));}}/*** 根据下标获取节点* @param index* @return*/private Node node(int index) {if(index < (size >> 1)) {Node x = first;for(int i = 0; i < index; i++) {x = x.next;}return x;}else {Node x = last;for(int i = size - 1; i > index; i--) {x = x.prev;}return x;}}/*** 根据下标获取元素* @param index* @return*/public Object get(int index) {checkElementIndex(index);return node(index).item;}/*** 删除元素* @param x* @return*/private Object unlink(Node x) {Object element = x.item;Node next = x.next;Node prev = x.prev;if(prev == null) {first = next;}else {prev.next = next;x.prev = null;}if(next == null) {last = prev;}else {next.prev = prev;x.next = null;}x.item = null;size--;return element;}/*** 根据下标删除元素* @param index* @return*/public Object remove(int index) {checkElementIndex(index);return unlink(node(index));}/*** 根据元素删除* @param o* @return*/public boolean remove(Object o) {if(o == null) {for(Node x = first; x != null; x = x.next) {if(x.item == null) {unlink(x);return true;}}}else {for(Node x = first; x != null; x = x.next) {if(o.equals(x.item)) {unlink(x);return true;}}}return false;}}class Node {Node prev;Object item;Node next;public Node() {}public Node(Node prev, Object item, Node next){this.prev = prev;this.item = item;this.next = next;} }

 

总结

以上是生活随笔为你收集整理的028_自己实现一个LinkedList的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。