package com.hyc.test.linked;
import org.w3c.dom.Node;
import sun.tools.tree.ThisExpression;
import java.net.NetworkInterface;
/**
* 类说明：基于双向链表实现
*
* @author hyc
* @version 1.0
* @date 2021/9/21 11:14
*/
public class MyDoubleLinkedList<E> implements Mylist<E> {
/**
* 定义双向链表的节点对象
*
* @param <E>
*/
class Node<E> {
// 前一个节点对象
Node<E> prev;
// 记录元素
E item;
//记录下一个节点对象
Node<E> next;
public Node(Node<E> prev, E item, Node<E> next) {
this.prev = prev;
this.item = item;
this.next = next;
}
}
private Node head; // 记录头节点
private Node tail;// 记录尾节点
private int size; // 记录个数
// 添加元素
@Override
public void add(E element) {
// 向尾部添加节点
this.linkLast(element);
}
/**
* 向尾部添加节点
*/
private void linkLast(E element) {
Node<E> t = this.tail;
Node<E> node = new Node<>(t, element, null);
this.tail = node;
if (t == null) {
this.head = node;
} else {
t.next = node;
}
this.size++;
}
//对index的合法性进行校验
private void checkIndex(int index) {
if (!(index >= 0 && index < this.size)) {
throw new IndexOutOfBoundsException("index" + index + "size" + size);
}
}
//根据位置查找节点对象
private Node<E> getNode(int index) {
// 判断当前位置距离头或着尾更近
if (index < (this.size >> 1)) {
Node<E> node = this.head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else { // 更靠近尾部
Node<E> node = this.tail;
for (int i = this.size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
//根据指定位置获取元素
@Override
public E get(int index) {
//对index的合法性进行校验
this.checkIndex(index);
// 根据位置查找节点对象
Node<E> node = this.getNode(index);
return node.item;
}
//返回元素的个数
@Override
public int size() {
return this.size;
}
//删除元素,根据位置删除
@Override
public E remove(int index) {
// 对index合法性校验
this.checkIndex(index);
// 根据位置获取节点对象
Node<E> node = this.getNode(index);
// 获取节点元素
E item = node.item;
// 判断当前节点是否为头节点
if (node.prev == null) {
this.head = node.next;
} else {
// 当前节点的前一个节点的前驱与当前节点的下一个节点后继节点的挂接
node.prev.next = node.next;
}
if (node.next == null) {
this.tail = node.prev;
} else {
// 完成当前节点的直接后继节点与当前节点的直接前驱节点的挂接
node.next.prev = node.prev;
}
// 当前节点断掉与直接前驱节点的连接
node.prev = null;
//当前节点断掉与直接后继节点的连接
node.next = null;
// 把元素滞空，目的加快垃圾回收！
node.item = null;
// 当前个数的-
this.size--;
// 返回元素
return item;
}
// 双向链表头添加元素
public void addFirst(E element) {
this.linkedFirst(element);
}
private void linkedFirst(E element) {
// 获取头节点
Node head = this.head;
Node<E> node = new Node<>(null, element, head);
// 将
this.head = node;
// 判断当前节点是空
if (head == null) {
this.tail = node;
} else {
head.prev = node;
}
this.size++;
}
// 在链表的尾部添加元素！
public void addLast(E element){
this.linkLast(element);
}
/**
* 测试方法
*
* @param args
*/
public static void main(String[] args) {
MyDoubleLinkedList<String> myDoubleLinkedList = new MyDoubleLinkedList<>();
myDoubleLinkedList.add("a");
myDoubleLinkedList.add("b");
myDoubleLinkedList.add("c");
myDoubleLinkedList.add("d");
myDoubleLinkedList.addLast("1111");
myDoubleLinkedList.addFirst("ada");
myDoubleLinkedList.remove(1);
for (int i = 0; i < myDoubleLinkedList.size(); i++) {
System.out.println(myDoubleLinkedList.get(i));
}
}
}
package com.hyc.test.linked;
/**
* 类说明：基于链表结构的方法API定义
*
* @author hyc
* @version 1.0
* @date 2021/9/21 09:58
*/
public interface Mylist<E> {
// 添加元素
void add(E element);
// 通过index获取元素
E get(int index);
// 获取元素的多少
int size();
// 根据元素位置删除元素
E remove(int index);
}
