Node
增加 pre 前驱 指向上一个节点
package _09_Linear.list;
/*节点*/!
public class ListNode {
Object data;//数据
ListNode next;//指向下一个节点的指针
ListNode pre;
public ListNode(Object data) {//初始化构造器
this.data = data;
}
}
DoublLinkedList
其head和tail都是空的 也就是如下定义的first和last
所有元素起于first.next 止于last
其中数据的增加
换四个linked
last.pre.next = newNode;//倒数第二个指向新的
newNode.next = last;//新的尾巴 指向 最后一个
newNode.pre = last.pre;//新的头指向 上次最后一个的前面一个
last.pre = newNode;//最后一个的头 指向新的
在删除 元素后 使得p.next p.pre =null 便于节约资源被CG清理
package _09_Linear.list;
public class DoubleLinkList implements MyList {
private ListNode first = new ListNode(null);//head
private ListNode last = new ListNode(null);//tail
private int size;
public DoubleLinkList() {//初始化两个 亚元
first.next = last;
last.pre = first;
}
/**
* 加到 node:last 之前
* 维护四条线
*
* @param element
*/
@Override
public void add(Object element) {
ListNode newNode = new ListNode(element);
last.pre.next = newNode;//倒数第二个指向新的
newNode.next = last;//新的尾巴 指向 最后一个
newNode.pre = last.pre;//新的头指向 上次最后一个的前面一个
last.pre = newNode;//最后一个的头 指向新的
size++;
}
@Override
public void delete(Object element) {
ListNode p = first.next;
while (p != last) {//终止于 亚元
if (p.data.equals(element)) {//当前p 匹配到了
size--;
p.pre.next = p.next;
p.next.pre = p.pre;
}
p = p.next;//滑动指向下一个节点
}
}
@Override
public void delete(int index) {
if (index < 0 || index >= size) {
return;//索引超出 [0,size)
}
int i = 0;
ListNode p = first.next;
while (p != last) {
if (i == index) {
size--;
p.pre.next = p.next;
p.next.pre = p.pre;
p.next = null;
p.pre = null;
break;
}
i++;
p = p.next;
}
}
@Override
public void update(int index, Object newElement) {
if (index < 0 || index >= size) {
return;//索引超出 [0,size)
}
int i = 0;
ListNode p = first.next;
while (p != last) {
if (i == index) {
p.data = newElement;
break;
}
i++;
p = p.next;
}
}
@Override
public boolean contains(Object target) {
ListNode p = first.next;
while (p != last) {
if (p.data.equals(target)) {
return true;
}
p = p.next;
}
return false;
}
@Override
public Object at(int index) {
if (index < 0 && index >= size) {
return null;
}
int i = 0;
ListNode p = first.next;
while (p != last) {
if (i == index) {
return p.data;
}
p = p.next;
i++;
}
return null;
}
@Override
public int indexOf(Object element) {
ListNode p = first.next;
int i = 0;
while (p != last) {
if (p.data.equals(element)) {
return i;
}
p = p.next;
i++;
}
return -1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
ListNode p = first.next;
while (p != last) {
sb.append(p.data).append(p.next != last ? "," : "");
p = p.next;
}
sb.append("]");//这么写的原因是 如果为空 就[] 不然写到while 里面 while不判定就gg
return "DoubleLinkList{" +
"elements=" + sb.toString() +
"size=" + size +
'}';
}
}
Test
package _09_Linear.list;
import org.junit.Test;
public class DoubleLinkListTest {
DoubleLinkList list = new DoubleLinkList();
@Test
public void add() {
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
System.out.println(list);
}
@Test
public void delete() {
add();
System.out.println("deleteTest:");
list.delete("a");
System.out.println(list);
list.delete("e");
System.out.println(list);
}
@Test
public void delete1() {
add();
System.out.println("deleteTestOfIndex:");
list.delete(1);
System.out.println(list);
}
@Test
public void update() {
add();
list.update(1,'D');
System.out.println(list);
}
@Test
public void contains() {
add();
System.out.println(list.contains("b"));
}
@Test
public void at() {
add();
System.out.println(list.at(4));
}
@Test
public void indexOf() {
add();
System.out.println(list.indexOf("b"));
}
}
本文作者:Author: 寒光博客
文章标题:[java] 双向链表 DoubleLinkedList
本文地址:https://dxoca.cn/dataStructure/283.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/dataStructure/283.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
把 gc写成 cg 我也是个人才 ̄﹃ ̄
非技术的路过。
ヾ(≧∇≦*)ゝ
韬光养晦,静待时机
没有喜欢上一个人难诶~~