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

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

节点类

 

/**
 * 
 */
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 {

		}
	}
}