-
如上,因为每个节点中只是保留了你下一个节点的地址,如果你遍历到了这个节点,这个节点就是你要删除的节点,那么你需要做的是把上一个节点和下一个节点链接起来,但是你遍历到此节点后,你上一个节点的信息已经遍历过去了,回不去了,所以我们就需要额外的保存已经遍历过的上一个节点
public class MyLinkedList<T> {
//添加的数据的个数
private int size;
//头指针
private Node<T> head;
//尾指针
private Node<T> tail;
public MyLinkedList() {
//初始化时候,头指针为空
head = new Node<>(null,null);
//因为没有元素,所以头指针尾指针是一个
tail = head;
}
//添加元素
public void add(int index ,T element) {
int i = -1;
for (Node<T> x = head; x != null; x = x.behind) {
if (i == index -1){
Node<T> next = x.behind;
x.behind = new Node<>(next,element);
break;
}
i ++;
}
size ++;
}
//增加元素
public void addLast(T element){
//如果头指针指向都是空的那么这个肯定是一个空链表
if (head.behind == null){
//空链表添加,就是新建节点的过程,新建的节点由于是第一个,那么他的后面是没有节点的
head.behind = new Node<>(null,element);
//就一个节点,尾指针就指向这个唯一节点
tail = head.behind;
}else {
//证明链表不为空,由于是在最后添加操作
//需要将tail暂时保存
Node<T> node = tail;
//tail指向新节点
tail = new Node<>(null,element);
//原来最后一个节点就是现在的尾指针指向的节点
node.behind = tail;
}
size ++;
}
//增加元素
public void addFirst(T element){
//之前跟addLast一致
if (head.behind == null){
head.behind = new Node<>(null,element);
tail = head.behind;
}else {
//向最开始添加节点,那么就需要保存最开始节点的引用
Node<T> node = head.behind;
//然后头指针指向最新插入的节点,该节点的构造方法中指向原来第一个节点
head.behind = new Node<>(node,element);
}
size ++ ;
}
//删除元素
public void remove(T element){
//空链表直接返回
if (null == head.behind) return;
Node<T> per; //这就是文章中说的,暂时保存前一个节点引用的
//第一个节点
Node<T> node = head.behind;
//头指针
per = head;
while (true){
//如果节点的数据与删除数据一致
if (node.element.equals(element)){
//==
//就是该节点的前一个节点指向该节点的下一个节点
per.behind = node.behind;
//删除完成
size --;
break;
}else {
//如果不一致,就需要将这个节点暂时保存
per = node ;
//如果这个节点没有下面的节点了,代表结尾了
if (node.behind == null){
//tail node.behind == null & !equals = no node
//到尾节点了,而且尾节点的数据与传入不一致,代表整个链表没有此数据
//退出
break;
}else {
//代表此node还有下一个节点
//那么就移动指向,移到下一个节点再while判断
node = node.behind;
}
}
}
}
//跟上面的方法大同小异,而且比上面的逻辑简单
public void remove(int index){
if (null == head.behind) return;
Node<T> per;
Node<T> node = head.behind;
per = head;
for (int i = 0; i <= index; i++) {
if (i == index){
//==
per.behind = node.behind;
break;
}else {
per = node ;
if (node.behind == null){
//tail node.behind == null & !equals = no node
break;
}else {
node = node.behind;
}
}
}
}
//修改元素
public void update(int index,T element){
//为什么是-1.因为下面的循环是从head头指针开始的,头指针是不算数的
int i = -1;
for (Node<T> x = head; x != null; x = x.behind) {
if (i == index){
x.element = element;
break;
}
i++;
}
}
//查找元素
public int getIndex(T element){
if (head.behind == null )
return -1;
int i = 0 ;
for (Node<T> x = head.behind; x != null; x = x.behind) {
if (x.element.equals(element)){
return i;
}
i++;
}
return -1;
}
//是否包含某个元素
public boolean contains(T element){
if (head.behind == null )
return false;
for (Node<T> x = head.behind; x != null; x = x.behind) {
if (x.element.equals(element)){
return true;
}
}
return false;
}
//元素个数
public int getSize() {
return size;
}
//代表图中的data+addr部分
private class Node<T>{
Node<T> behind;//指向后面元素的指针
T element; //当前数据
public Node(Node<T> behind, T element) {
this.behind = behind;
this.element = element;
}
}
@Override
public String toString() {
if (head == null){
return "{}";
}
Node<T> firstNode = head.behind;
Node<T> node = new Node<>(firstNode.behind,firstNode.element);
StringBuilder buffer = new StringBuilder();
while (true){
if (node == null){
break;
}else {
buffer.append(node.element + " , ");
node = node.behind;
}
}
return buffer.toString();
}
}
-
测试
public static void main(String[] args) {
MyLinkedList<String> linkedList = new MyLinkedList<>();
linkedList.addLast("1");
linkedList.addLast("2");
linkedList.addLast("3");
linkedList.addLast("4");
linkedList.addLast("5");
linkedList.addFirst("0");
linkedList.addFirst("-1");
System.out.println(linkedList);
linkedList.remove("0");
System.out.println(linkedList);
linkedList.remove(0);
System.out.println(linkedList);
linkedList.remove(4);
System.out.println(linkedList);
linkedList.add(2,"s");
System.out.println(linkedList);
linkedList.add(4,"p");
System.out.println(linkedList);
linkedList.update(0,"x");
System.out.println(linkedList);
linkedList.update(3,"z");
System.out.println(linkedList);
int x = linkedList.getIndex("x");
System.out.println(x);
int z = linkedList.getIndex("z");
System.out.println(z);
boolean x1 = linkedList.contains("x");
System.out.println(x1);
System.out.println(linkedList.contains("2"));
System.out.println(linkedList.contains("yyy"));
}
-
结果
-1 , 0 , 1 , 2 , 3 , 4 , 5 ,
-1 , 1 , 2 , 3 , 4 , 5 ,
1 , 2 , 3 , 4 , 5 ,
1 , 2 , 3 , 4 ,
1 , 2 , s , 3 , 4 ,
1 , 2 , s , 3 , p , 4 ,
x , 2 , s , 3 , p , 4 ,
x , 2 , s , z , p , 4 ,
0
3
true
true
false
- 里面的内部类Node,就是每个节点,里面存放了指向和数据
- 其实实现的重点在于add方法,如果你可以将上面的单链表的理解了,那么下面的就跟闹着玩似的,自我感觉双向的比单向的好写
-
上面是新增元素的一个过程,拆除原来的互相引用,而转链接到新元素到,那么删除的话,就是一个反过程,将要被删除的元素上的所以指向删除,然后该元素的前一个元素引用该元素后面的元素,后面的元素引用前面的元素,如果该元素为a,那么就是a+1互相引用a-1,知道了最麻烦的步骤,下面就是实现代码
public class DoubleLink<T> {
private int size;
private Node<T> head;
private Node<T> tail;
public DoubleLink() {
head = new Node<>();
tail = new Node<>();
head.front = tail;
head.next = tail;
tail.front = head;
tail.next = head;
}
private class Node<T> {
private Node<T> front;
private T element;
private Node<T> next;
public Node() {
}
public Node(Node<T> front, T element, Node<T> next) {
this.front = front;
this.element = element;
this.next = next;
}
@Override
public String toString() {
return "" + element;
}
}
//增
public void addLast(T element) {
if (0 == size) {
Node<T> node = new Node<>(head, element, tail);
head.next = node;
tail.front = node;
} else {
Node<T> tailNodeFront = tail.front;
Node<T> node = new Node<>(tailNodeFront, element, tail);
tailNodeFront.next = node;
tail.front = node;
}
size++;
}
public void addFirst(T element) {
if (0 == size) {
Node<T> node = new Node<>(head, element, tail);
head.next = node;
tail.front = node;
} else {
Node<T> headNextNode = head.next;
Node<T> node = new Node<T>(head, element, headNextNode);
head.next = node;
headNextNode.front = node;
}
size++;
}
public void add(int index, T element) {
if (0 == size) {
Node<T> node = new Node<>(head, element, tail);
head.next = node;
tail.front = node;
} else {
int i = -1;
for (Node<T> node = head; node != null; node = node.next) {
if (i == index) {
Node<T> front = node.front;
Node<T> newNode = new Node<>(front, element, node);
front.next = newNode;
node.front = newNode;
break;
}
i++;
}
}
size++;
}
//删
public void remove(T element){
for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
if (node.element.equals(element)){
Node<T> front = node.front;
Node<T> next = node.next;
front.next = next;
next.front = front;
}
}
size --;
}
//改
public void update(int index ,T element){
int i = 0;
for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
if (i == index){
node.element = element;
}
i++;
}
}
//查
public int getIndex(T element){
int i = 0;
for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
if (node.element.equals(element)){
return i;
}
i++;
}
return -1;
}
//包含
public boolean contains(T element){
for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
if (node.element.equals(element)){
return true;
}
}
return false;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (Node<T> node = head.next; node != null&& node.element != null; node = node.next) {
builder.append(node.toString()+" ");
}
return builder.toString();
}
}
-
测试
public static void main(String[] args) {
DoubleLink<String> doubleLink = new DoubleLink<>();
doubleLink.addLast("1");
doubleLink.addLast("2");
doubleLink.addLast("3");
doubleLink.addLast("4");
System.out.println(doubleLink);
doubleLink.addFirst("0");
doubleLink.addFirst("-1");
System.out.println(doubleLink);
doubleLink.add(2,"ppp");
doubleLink.add(0,"-2");
System.out.println(doubleLink);
doubleLink.remove("ppp");
System.out.println(doubleLink);
doubleLink.remove("0");
System.out.println(doubleLink);
doubleLink.remove("-1");
System.out.println(doubleLink);
doubleLink.remove("-2");
System.out.println(doubleLink);
doubleLink.update(0,"11");
doubleLink.update(2,"33");
System.out.println(doubleLink);
System.out.println(doubleLink.getIndex("2"));
System.out.println(doubleLink.getIndex("2xx"));
System.out.println(doubleLink.contains("11"));
System.out.println(doubleLink.contains("11x"));
}
-
结果
1 2 3 4
-1 0 1 2 3 4
-2 -1 0 ppp 1 2 3 4
-2 -1 0 1 2 3 4
-2 -1 1 2 3 4
-2 1 2 3 4
1 2 3 4
11 2 33 4
- 只要会写这两个了,那么其他两个也就会了,好了到这就算告一段落了,如果有错,请及时评论提醒我哈!希望能给你带去帮助
