LinkedList
使用场景:
如果仅在两端操作数据，用LinkedList
数据量较小时（100以内），频繁增删数据用LinkedList
双向链表：两端效率高，越往中间效率越低
创新互联一直通过网站建设和网站营销帮助企业获得更多客户资源。 以"深度挖掘，量身打造，注重实效"的一站式服务，以成都网站设计、成都网站建设、移动互联产品、全网整合营销推广服务为核心业务。十多年网站制作的经验，使用新网站建设技术，全新开发出的标准网站，不但价格便宜而且实用、灵活，特别适合中小公司网站制作。网站管理系统简单易用，维护方便，您可以完全操作网站资料，是中小公司快速网站建设的选择。
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, 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;
}
}
}
