Java如何实现双向链表功能

Java如何实现双向链表功能

双向链表实现

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。注意：在操作双向链表时，不要去移动指向前驱节点和后继节点的指针，而是重新定义指向头尾的指针进行移动。*

环境

IDEA

自定义操作接口

双向链表。

public interface MyList {

void add(E node);

E get(int index);

E remove(int index);

int size();

}

实现类

public class MyDoublyLinkList implements MyList {

/**

* 定义双向链表节点

*/

class Node {

Node prev;

E item;

Node next;

public Node(Node prev, E item, Node next) {

this.prev = prev;

this.item = item;

this.next = next;

}

}

private Node head;

private Node tail;

private int size;

/**

* 将节点添加到尾部

*

* @param item

* @return

*/

@Override

public void add(E item) {

this.linkLast(item);

}

/**

* 添加一个元素到尾部

*

* @param e

*/

private void linkLast(E e) {

//获取tail

Node node = this.tail;

//创建一个node

Node newNode = new Node<>(node, e, null);

this.tail = newNode;

if (node == null)

this.head = newNode;

else

node.next = newNode;

size++;

}

/**

* 获取指定位置元素

* @param index

* @return

*/

@Override

public E get(int index) {

//校验index是否合法

checkIndex(index);

//获取index元素

return getNode(index).item;

}

/**

* 校验index合法性

*

* @param index

*/

private void checkIndex(int index) {

if (!(index >= 0 && index < this.size))

throw new IndexOutOfBoundsException(Strhttp://ing.format("index out of bounds,index:%s,size:%s", index, this.size));

}

/**

* 获http://取nodIHBkNrBDe

*

* @param index

* @return

*/

private Node getNode(int index) {

if (index > (size >> 1)) {

Node node = this.tail;

//从tail向前遍历

for (int i = size - 1; i > index; i--) {

node = node.prev;

}

return node;

} else {

//从head向后遍历

Node node = this.head;

for (int i = 0; i < index; i++) {

node = node.next;

}

return node;

}

}

/**

* 删除指定位置元素

*

* @param index

* @return

*/

@Override

public E remove(int index) {

//判断index合法性

this.checkIndex(index);

Node node = getNode(index);

E e = node.item;

//判断是否为头节点

if (node.prev == null) {

this.head = node.next;

} else {

node.prev.next = node.next;

node.prev = null;

}

//判断是否为尾节点

if (node.next == null) {

this.tail = node.next;

} else {

node.next.prev = node.prev;

node.next = null;

}

node.item = null;

size--;

return e;

}

/**

* 获取链表长度

*

* @return

*/

@Override

public int size() {

return this.size;

}

}

测试方法

public static void main(String[] args) {

MyList stringMyList = new MyDoublyLinkList<>();

System.out.println(stringMyList.size());

stringMyList.add("a");

stringMyList.add("b");

stringMyList.add("c");

stringMyList.add("d");

System.out.println(stringMyList.size());

String re = stringMyList.remove(1);

System.out.println(re);

for (int i = 0; i < stringMyList.size(); i++) {

System.out.println(stringMyList.get(i));

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。