数据结构--线性表双向链表的实现

目录

思路设计

总体思维导图

插入部分

头插法+尾插法

任意位置插入

删除部分

头结点

尾节点

中间节点

只有头结点且删除的就是头结点

​编辑

清空链表部分

遍历清空链表的所有节点

不遍历清空

各部分代码

Main部分

MyListedList部分

IndexOutOfException部分

总结

---

思路设计

设计Main，MyListedList，IndexOutOfException 三个文件。

Ma负责主函数的运行，MyList负责各种方法，IndexOut负责输入错误的提示。

总体思维导图

插入部分

头插法+尾插法

任意位置插入

删除部分

头结点

尾节点

中间节点

只有头结点且删除的就是头结点

清空链表部分

遍历清空链表的所有节点

不遍历清空

各部分代码

Main部分

public class Main {public static void main(String[] args) {//这个是顺序表的写法，现在是双向链表//MyListedList<Integer> myListedList= new MyListedList();MyListedList myListedList= new MyListedList();myListedList.addFirst(1);myListedList.addFirst(2);myListedList.addFirst(3);myListedList.addFirst(4);/*myListedList.addLast(1);myListedList.addLast(2);myListedList.addLast(3);myListedList.addLast(4);*///System.out.println(myListedList.size());//System.out.println(myListedList.contains(10));//myListedList.display();//myListedList.addIndex(0,99);//myListedList.display();myListedList.removeAllKey(1);myListedList.clear();myListedList.display();}
}

MyListedList部分

public class MyListedList {static class ListNode{private int val;private ListNode prev;private ListNode next;//重写构造方法得以调用//才能保证下面传入的data能使用//ListNode node = new ListNode(data);public ListNode(int val) {this.val = val;}}//双向链表的头节点public ListNode head;//双向链表的尾节点public ListNode last;//得到单链表的长度//size,display,contains都是要遍历定义头指针public int size(){ListNode cur = head;int count = 0;while (cur != null){count++;cur = cur.next;}return count;}public void display(){//遍历定义一个头结点指针，让其不断往后走ListNode cur = head;while (cur != null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data){ListNode node = new ListNode(data);//如果插入的节点的前后指针都是空的话//要修改链表里面的头尾指针if(head == null){head = node;last = node;}else {//先改变next再改变pervnode.next = head;head.prev = node;head = node;}}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if(head == null){head = node;last = node;}else {last.next = node;node.prev = last;last = node;//或者 last = last.next}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){checkIndex(index);if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}//声明curListNode cur = seachIndex(index);ListNode node = new ListNode(data);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}//定义cur找到插入的位置private ListNode seachIndex(int index){ListNode cur = head;while (index != 0){cur = cur.next;index--;}return cur;}private void checkIndex(int index){if (index < 0 || index > size()){//可以自定义抛出RuntimeException（运行异常）一个异常throw new IndexOutOfException("index 不合法！"+index);}}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;if(head == null) {head = cur;last = cur;}while (cur != null){if(cur.val == key){//如果要删除的是头结点if(cur == head){//移动位置head = head.next;//只有头节点，且其就是删除的节点if(head != null){head.prev = null;}else {last = null;}}else {//删除中间节点if(cur.next != null){cur.prev.next = cur.next;cur.next.prev = cur.prev;} else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}return;}else {cur = cur.next;}}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;if(head == null) {head = cur;last = cur;}while (cur != null){if(cur.val == key){//如果要删除的是头结点if(cur == head){//移动位置head = head.next;//只有头节点，且其就是删除的节点if(head != null){head.prev = null;}else {last = null;}}else {//删除中间节点if(cur.next != null){cur.prev.next = cur.next;cur.next.prev = cur.prev;} else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}//删除key数据了之后往后走，查看//是否还有要删除的数据去遍历cur = cur.next;//return;}else {//就算这个数据不是我要删除的数据，我也往后走去遍历cur = cur.next;}}}public void clear(){ListNode cur = head;while (cur != null){ListNode curNext = cur.next;if(cur == null){cur = curNext;}else {cur.next = null;cur.prev = null;cur = curNext;}}head = null;last = null;}
}

IndexOutOfException部分

public class IndexOutOfException extends RuntimeException{//提供两个构造方法public IndexOutOfException() {}public IndexOutOfException(String message) {super(message);}
}

总结

部分方法大体上写法都大致相同，关键在于具体方法部分，比如：删除的节点就只有一个，而且这个要删除的节点就是头结点，那么这种特殊情况是在写完正常删除操作后，输入数据判断得到的结果，针对这样的情况要画图分析，一步一步慢慢思考如何设计程序代码，出错没有关系，再次调试画图看看有没有漏掉的地方，一次次修改相信最终会获得成功完成任务的代码。

数据结构的核心就是，代码容易写，思考最难想的一个学习过程，由此可见画图在帮助我们理清思路，规整代码写法的时候就尤为重要！

---

希望这篇博客能给读者在学习数据结构时提供一些帮助。