双向链表的代码实现

实现双向链表

package com.liuzhen;
//双向链表
public class Linked2<E> {
Node<E> first;// 头节点
Node<E> last;// 尾节点
int size;// 链表长度
/*
* 添加新结点（头插法）
*/
public void linkerFirst(E e) {
// 获取当前头结点
final Node<E> f = first;
// 创建新的头结点
final Node<E> newNode = new Node<E>(null, e, f);
// 设置链表的新头结点
first = newNode;
if (f == null) {
// 同时设置尾节点
last = newNode;
} else {
// 设置旧头结点的前驱=>新头结点
f.prev = newNode;
// 链表长度自增
size++;
}
}
// 尾插法
public void linkLast(E e) {
// 获取当前链表尾节点
final Node<E> l = last;
// 创建新的尾节点
final Node<E> newNode = new Node<E>(l, e, null);
// 设置新的尾结点
last = newNode;
if (l == null) {
// 同时设置头结点
first = newNode;
} else {
// 设置旧的尾结点的后继为新为新尾结点
l.next = newNode;
size++;
}
}
/*
* 根据下标位置查找结点
*/
public Node<E> node(int index) {
// 判断下标位置在上半区或下半区，进行折半查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
// 下半区
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}
/*
* 删除头结点
*/
public void removeFirst() {
// 获取头结点
final Node<E> f = first;
// 获取头节点的下一个结点
final Node<E> next = f.next;
// 清空头结点
f.iem = null;
f.next = null;
// 设置链表的头结点
first = next;
if (next == null) {
last = null;
} else {
next.prev = null;
// 链表长度自减
size--;
}
}
/*
* 删除尾巴节点
*/
public void removeLast() {
// 获取尾巴节点
final Node<E> l = last;
// 获取尾结点的前驱结点
final Node<E> prev = l.prev;
// 清空尾节点
l.iem = null;
l.prev = null;
// 设置尾节点
last = prev;
if (prev == null) {
first = null;
} else {
prev.next = null;
size--;
}
}
static class Node<E> {
E iem;// 数据域
Node<E> next;// 后继结点
Node<E> prev;// 前驱结点
// 构造方法
// 参数1：前驱结点
// 参数2：数据域
// 参数3：后继结点
public Node(Node<E> prev, E iem, Node<E> next) {
this.iem = iem;
this.next = next;
this.prev = prev;
}
}
}

测试类

package com.liuzhen;
import com.liuzhen.Linked2.Node;
public class Text2 {
public static void main(String[] args) {
Linked2<String> link = new Linked2<String>();
link.linkerFirst("A");// 头插法
link.linkerFirst("B");
link.linkerFirst("C");
link.linkerFirst("D");
link.linkerFirst("E");
link.linkLast("天");// 尾插法
link.linkLast("王");
link.linkLast("盖");
link.linkLast("地");
link.linkLast("虎");
//删除头结点
link.removeFirst();
//删除尾巴结点
link.removeLast();
for (Linked2.Node<String> node = link.first; node != null; node = node.next) {
System.out.println(node.iem);
}
Node<String> s = link.node(6);
System.out.println("第六个元素："+s.iem);
Node<String> s2 = link.node(9);
System.out.println("第9个元素："+s2.iem);
}
}

最后

以上就是稳重音响为你收集整理的双向链表的代码实现的全部内容，希望文章能够帮你解决双向链表的代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。