欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法与数据结构的复习——单链表、双端链表、双向链表

程序员文章站 2024-03-16 15:39:04
...

单链表只需要知道头节点就可以知道整个链表的数据。每个节点对象都会有一个数据域和下一节点的引用

节点类

 

/**
 * 
 */
package ch04;

/**
 * @author lixin
 * @date 2018年7月22日
 * @Description 节点类
 */

public class Node {
	//将属性设置为public访问,可以不写set、get方法!!!
	public long data;

	public Node next;

	public Node(long value) {
		this.data = value;
	}

	public void display() {
		System.out.print(this.data+" ");
	}

}

单链表的实现

/**
 * 
 */
package ch04;

/**
 * @author lixin
 * @date 2018年7月22日
 * @Description TODO
 */
public class LinkList {
	private Node first;

	public LinkList() {
		first = null;
	}

	// 向头结点后插入节点
	public void insert(long value) {
		Node node = new Node(value);
		if (first == null) {
			first = node;
		} else {
			// first代表第二节点可以直接
			// 在插入一个节点之后原来的第二节点应变成第三节点
			if (first.next != null) {
				node.next = first.next;
			}
			first.next = node;
		}

		// 向头结点前插入一个节点
		/*
		 * Node node = new Node(value); node.next = first; first = node;
		 */
	}

	// 删除头结点后的一个节点
	// 将头结点的next直接指向第三个
	// 垃圾回收机制会自动回收没有引用的数据
	public Node delete() {
		if (first == null) {
			return null;
		} else {
			Node temp = first.next;
			first.next = temp.next;
			return temp;
		}
	}

	// 显示当前链表所有数据
	public void show() {
		Node temp = first;
		while (temp != null) {
			temp.display();
			temp = temp.next;
		}
	}

	// 根据数据查找节点
	public Node find(long value) {
		Node temp = first;
		while (temp.data != value) {
			if (temp.next == null) {
				return null;
			}
			temp = temp.next;
		}
		return temp;
	}

	//根据数据删除节点
	public void deleteByData(long value) {
		Node temp = first;
		Node previous = first;
		while (temp.data != value) {
			if (temp.next == null) {
				System.out.println("元素不存在");
				break;
			}
			temp = temp.next;
			previous=temp;
		}
		if(temp==first){
			first=first.next;
		}else{
			first.next=temp.next;
		}
	}

	public static void main(String[] args) {
		LinkList linkList = new LinkList();
		linkList.insert(11);
		linkList.insert(13);
		linkList.insert(14);
		linkList.show();
		linkList.delete();
		System.out.println("------");
		linkList.show();
		System.out.println("------");
		System.out.println(linkList.find(11).data);
		System.out.println("------");
		linkList.deleteByData(33);
		linkList.show();
	}
}

双端链表的实现——

/**
 * 
 */
package ch05;

/**
 * @author lixin
 * @date 2018年7月22日
 * @Description 双端链表的实现
 */
public class DoubleEndLinkList {

	// 头结点
	private Node first;

	// 尾节点
	private Node last;

	public DoubleEndLinkList() {
		first = null;
		last = null;
	}

	// 向头节点前插入节点
	public void insertFromHead(long value) {
		Node node = new Node(value);
		if (first == null) {
			last = node;
		}
		node.next = first;
		first = node;
	}

	// 从尾节点插入注意当空值链表时头节点的设置
	public void insertFromEnd(long value) {
		Node node = new Node(value);
		if (first == null) {
			first = node;
		} else {
			last.next = node;
		}
		last = node;
	}

	// 从对头删除节点
	public void deleteFromHead() {
		if (first == null) {
		} else {
			first = first.next;
		}
	}

	// 显示当前链表所有数据
	public void show() {
		Node temp = first;
		while (temp != null) {
			temp.display();
			temp = temp.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		DoubleEndLinkList doubleEndLinkList = new DoubleEndLinkList();
		// 插入四个数
		doubleEndLinkList.insertFromEnd(11);
		doubleEndLinkList.insertFromEnd(12);
		doubleEndLinkList.insertFromEnd(13);
		doubleEndLinkList.insertFromEnd(14);
		doubleEndLinkList.show();
		// 从头插入一个
		doubleEndLinkList.insertFromHead(45);
		doubleEndLinkList.show();
		// 从尾插入一个
		doubleEndLinkList.insertFromEnd(55);
		doubleEndLinkList.show();
		// 从头删除一个
		doubleEndLinkList.deleteFromHead();
		doubleEndLinkList.show();
	}
}

双向链表的实现需要在节点类宋添加当前节点的上一个节点的引用

/**
 * 
 */
package ch05;

/**
 * @author lixin
 * @date 2018年7月22日
 * @Description TODO
 */
public class Node {
	
	public long data;

	public Node next;
	
	//上一节点专为双向链表使用
	public Node previous;
	
	public Node(long value) {
		this.data = value;
	}

	public void display() {
		System.out.print(this.data + " ");
	}
}

双向链表的实现

/**
 * 
 */
package ch05;

/**
 * @author lixin
 * @date 2018年7月22日
 * @Description 双向链表
 */
public class DoubleLinkList {

	private Node first;

	private Node last;

	public DoubleLinkList() {
		first = null;
		last = null;
	}

	/**
	 * 插入一个结点,在头节点插入
	 */
	public void insertBegin(long value) {
		Node node = new Node(value);
		if (first == null) {
			last = node;
		}
		first.previous = node;
		node.next = first;
		first = node;
	}

	/**
	 * 插入一个结点,在尾节点插入
	 */
	public void insertEnd(long value) {
		Node node = new Node(value);
		if (first == null) {
			first = node;
		} else {

		}
	}
}