双向链表的应用

---

双向链表的应用
1.使用带head头的双向链表实现
2.双向链表可以前后查找因为有pre，单向链表只能一个方向
3.增删方便，改查方便，利用编号；

---

【注】:因为查询和单链表类似所以就省去了双链表的查询。

package LinkedList;

public class DoubleLinkedListTest {
	public static void main(String[] args) {
		PersonNode p1 = new PersonNode(3, "韩愈", "男", "文学家");
		PersonNode p2 = new PersonNode(4, "李清照", "女", "词学家");
		PersonNode p3 = new PersonNode(1, "孙子", "男", "军事家");
		PersonNode p4 = new PersonNode(2, "刘备", "男", "战略家");

		DoubleLinkedList d = new DoubleLinkedList();
		
		d.addBySort(p1);
		d.addBySort(p2);
		d.addBySort(p3);
		d.addBySort(p4);

		d.upThisNode(new PersonNode(12, "貂蝉", "女", "砝码"));
		
		//d.delteThisNode(1);

		d.showList();

	}
}

class DoubleLinkedList {
	private PersonNode head = new PersonNode(0, "", "", "");

	// 添加->随机添加 ：添加到链表末尾
	public void add(PersonNode newNode) {
		PersonNode temp = head;
		while (true) {
			if (temp.next == null) {
				break;
			}
			temp = temp.next;
		}
		temp.next = newNode;
		newNode.pre = temp;
	}

	/**
	 * 
	 * @param node
	 */
	public void upThisNode(PersonNode node) {
		int id = node.id;
		boolean flag = false;
		PersonNode temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			if (temp.id == id) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.name = node.name;
			temp.job = node.job;
			temp.sex = node.sex;
		} else {
			// 没有找到这个节点
			System.out.println("没有找到这个节点");
		}
	}

	/**
	 * 
	 * @param id
	 */
	public void delteThisNode(int id) {
		if (head.next == null) {
			System.out.println("这个链表为空链表！");
			return;
		}
		PersonNode temp = head.next;
		boolean flag = false;
		while (true) {
			if (temp == null) {// 表示链表已经到达最后
				break;
			}
			if (temp.id == id) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.pre.next = temp.next;
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}

		} else {
			System.out.println("链表里没有编号为" + id + "的这个节点!");
		}

	}

	// 按照id大小顺序添加
	public void addBySort(PersonNode newPerson) {
		int id = newPerson.id;
		PersonNode temp = head;
		boolean flag = false;
		while (true) {
			// 没有找到情况
			if (temp.next == null) {
				break;
			}
			if (temp.next.id > id) {
				break;
			} else if (temp.next.id == id) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			System.out.println("此编号的节点已经存在");
		} else {
			// 这个地方可能会有点迷，但是在纸上分析一下会很快得出如下这些关系
			newPerson.next = temp.next;
			newPerson.pre = temp;
			temp.next = newPerson;
			newPerson.pre = temp;
		}
	}

	// 遍历链表
	public void showList() {
		PersonNode temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			System.out.println(temp);
			temp = temp.next;
		}
	}
}

//定义的节点
class PersonNode {
	public int id;
	public String name;
	public String sex;
	public String job;
	public PersonNode next;
	public PersonNode pre;

	public PersonNode(int id, String name, String sex, String job) {
		this.id = id;
		this.name = name;
		this.sex = sex;
		this.job = job;
	}

	@Override
	public String toString() {
		return "PersonNode [id=" + id + ", name=" + name + ", sex=" + sex + ", job=" + job + "]";
	}
}

本文地址：https://blog.csdn.net/mzy1711231996/article/details/107348324