目录
思路设计
总体思维导图
插入部分
头插法+尾插法
任意位置插入
删除部分
头结点
尾节点
中间节点
只有头结点且删除的就是头结点
编辑
清空链表部分
遍历清空链表的所有节点
不遍历清空
各部分代码
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再改变perv
node.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;
}
//声明cur
ListNode 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);
}
}
总结
部分方法大体上写法都大致相同，关键在于具体方法部分，比如：删除的节点就只有一个，而且这个要删除的节点就是头结点，那么这种特殊情况是在写完正常删除操作后，输入数据判断得到的结果，针对这样的情况要画图分析，一步一步慢慢思考如何设计程序代码，出错没有关系，再次调试画图看看有没有漏掉的地方，一次次修改相信最终会获得成功完成任务的代码。
数据结构的核心就是，代码容易写，思考最难想的一个学习过程，由此可见画图在帮助我们理清思路，规整代码写法的时候就尤为重要！
希望这篇博客能给读者在学习数据结构时提供一些帮助。
