JAVA自己实现LinkedList
发布时间：2020-12-15 08:01:36 所属栏目：Java 来源：网络整理
导读：package 集合.list.LinkedList; public class MyLinkedList { //默认长度为0 private int size = 0; Node head = null; Node tail = null; public MyLinkedList() { } //添加元素的方法 public void add(Object obj) { //创建Node Node node = new Node(obj,
package 集合.list.LinkedList; public class MyLinkedList { //默认长度为0 private int size = 0; Node head = null; Node tail = null; public MyLinkedList() { } //添加元素的方法 public void add(Object obj) { //创建Node Node node = new Node(obj,null,null); //先判断之前的尾部节点 if (size == 0) { this.head = node; } else { Node temp; temp = this.tail; temp.next = node; node.prev = temp; } this.tail = node; size++; } //插入元素 public void add(int index,Object obj) { //先判断索引是否合法 if (index > size || index < 0) { throw new IndexOutOfBoundsException(); } //判断插入位置 if (index == size) { this.add(obj); return; } //创建Node Node node = new Node(obj,null); Node temp = null; //如果插入是头部 if (index == 0) { temp = this.head; this.head = node; node.next = temp; temp.prev = node; } else { // 如果插入中间位置 Node insertNode = indexOf(index); Node prev = insertNode.prev; node.prev = prev; node.next = insertNode; prev.next = node; insertNode.prev = node; } size++; } //删除指定索引元素 public void remove(int index) { Node n; if (index == 0) { n = head.next; head = n; n.prev = null; } else if (index == size - 1) { n = tail.prev; tail = n; n.next = null; } else { Node node = indexOf(index); Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; // node.prev = null; //node.next = null; } size--; } //删除第一个出现的元素 public void remove(Object obj) { int index = indexOf(obj); if (index != -1) { remove(index); } } //查找元素返回索引 public int indexOf(Object obj) { //获取头节点 Node node = head; for (int i = 0; i < size; i++) { if (node.value == obj || node.value != null && node.value.equals(obj)) { return i; } node = node.next; } return -1; } //查找指定索引的元素 public Node indexOf(int index) { if (index == 0) { return head; } if (index == size - 1) { return tail; } Node n; if (index <= size / 2) { //前一半 n = head; for (int i = 1; i < index; i++) { n = n.next; } } else { n = tail; for (int i = size - 2; i >= index; i--) { n = n.prev; } } return n; } //判断是否包含元素 public boolean cotains(Object obj) { return indexOf(obj) != -1; } //获取长度 public int getSize() { return size; } //判断是否为空 public boolean isEmpty() { return size == 0; } //清空链表 public void clear() { //设置头尾节点为null,size=0 this.tail = null; this.head = null; size = 0; } //通过索引修改数据 public void set(int index,Object obj) { //先判断索引是否合法 if (index > size || index < 0) { throw new IndexOutOfBoundsException(); } indexOf(index).value = obj; } //获取子链表 public MyLinkedList sublist(int fromIndex,int toIndex) { //判断越界 //先判断索引是否合法 if (toIndex > size || fromIndex < 0) { throw new IndexOutOfBoundsException(); } MyLinkedList sublist = new MyLinkedList(); //先获取fromIndex处的节点 Node node = indexOf(fromIndex); for (int i = fromIndex; i < toIndex; i++) { //将对于节点处的值加入到子链表中 sublist.add(node.value); //每次循环需要改变节点 node = node.next; } return sublist; } //重写toString @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); //获取节点 Node node = head; for (int i = 0; i < size; i++) { if (i != size - 1) { sb.append(node.value).append(","); } else { sb.append(node.value); } node = node.next; } sb.append("]"); return sb.toString(); } //定义节点内部静态类 private static class Node { //节点的数据 Object value; //节点的下一个地址 Node next; //上一个地址 Node prev; Node(Object value,Node prev,Node next) { this.value = value; this.next = next; this.prev = prev; } } }
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |