单向链表存储结构及反转

单向链表存储结构及反转

单向链表存储结构

import java.util.Stack;

/**
 * 
 * @ClassName SingleLinkedListDemo
 * @Description
 * @Author 明月照海心
 * @Date 2020年7月20日 下午8:21:13
 */
public class SingleLinkedListDemo {

	public static void main(String[] args) {
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		singleLinkedList.add(20);
		singleLinkedList.add("hello");
		singleLinkedList.add(40);
		singleLinkedList.add("mingyue");
		singleLinkedList.add(60);

		System.out.println("----------遍历所有元素----------");
		singleLinkedList.showList();

		System.out.println("元素的个数：" + singleLinkedList.getSize());

		System.out.println("----------删除一个元素----------");
		Object remove = singleLinkedList.remove(60);
		System.out.println("移除的元素是:" + remove);
		singleLinkedList.showList();

		System.out.println("元素的个数：" + singleLinkedList.getSize());

		singleLinkedList.reverse();
		System.out.println("----------反转后的元素----------");
		singleLinkedList.showList();

		System.out.println("----------倒序打印元素----------");
		singleLinkedList.reversePint();

	}
}

class SingleLinkedList {

	// 定义头结点
	private Node first = new Node(null, null);

	private int size;

	public int getSize() {
		return size;
	}

	/**
	 * 添加元素
	 * 
	 * @param e
	 */
	public void add(Object e) {

		// 头结点不能动，需要辅助结点进行操作
		Node head = first;
		// 新建结点将元素存进去
		Node node = new Node(e, null);
		while (true) {
			// 如果当前节点的next为空，则将next指向当前节点
			if (head.next == null) {
				head.next = node;
				size++;
				break;
			}

			head = head.next;
		}
	}

	/**
	 * 删除元素
	 * 
	 * @param e
	 * @return
	 */
	public Object remove(Object e) {

		// 头结点不能动，需要辅助结点进行操作
		Node head = first;
		// 判断是否有元素
		if (head.next == null) {
			System.out.println("链表中没有元素！");
			return null;
		}

		// 遍历所有节点
		while (true) {

			if (head.next == null) {
				System.out.println("在链表中没有找到当前元素！");
				break;
			}

			// 查看当前节点元素是否和形参元素相同
			if (e == head.next.item || e.equals(head.next.item)) {
				Node removeNode = head.next;
				head.next = removeNode.next;
				size--;
				return removeNode.item;
			}
			head = head.next;
		}
		return null;
	}

	/**
	 * 显示所有元素
	 */
	public void showList() {

		// 头结点不能动，需要辅助结点进行操作
		Node head = first;

		// 判断是否有元素
		if (head.next == null) {
			System.out.println("链表中没有元素！");
		}
		while (true) {

			// 如果当前节点的next为空，则结束循环
			if (head.next == null) {
				break;
			}
			head = head.next;
			System.out.println(head.item);
		}
	}

	/**
	 * 节点内部类
	 * 
	 * @ClassName Node
	 * @Description
	 * @Author 明月照海心
	 * @Date 2020年7月20日 下午8:25:50
	 */
	private class Node {
		Object item;
		Node next;

		Node(Object element, Node next) {
			this.item = element;
			this.next = next;

		}
	}
}

单向链表的反转

/**
	 * 反转链表
	 */
	public void reverse() {
		// 获取当前结点
		Node cur = first.next;
		// 定义一个反转后的头结点
		Node reverseFirstNode = new Node(null, null);
		// 当前元素个数小于2不需要反转
		if (size < 2) {
			return;
		}
		while (cur != null) {

			// 此处有点绕
			// 首先取出当前节点的下个节点（如果不取出，下行代码会覆盖其值）
			Node next = cur.next;
			// 当前元素的下一个节点指向所定义头结点的下一个节点（比如插队的时候需要和当前插入位置所在的人说一声）
			cur.next = reverseFirstNode.next;
			// 定义的头结点指向当前节点
			reverseFirstNode.next = cur;
			// 节点继续向下移动
			cur = next;

		}
		// 当前节点替换所定义的头结点
		first.next = reverseFirstNode.next;

	}

单向链表的反转输出

/**
	 * 使用栈实现链表的倒序输出
	 */
	public void reversePint() {

		// 获取当前结点
		Node cur = first.next;
		if (cur == null) {
			System.out.println("当前链表为空！");
			return;
		}
		// 创建栈对象
		Stack<Object> stack = new Stack<>();

		while (cur != null) {
			// 当前元素进栈 (此处用add方法一样，add返回boolean，push返回当前元素)
			stack.push(cur.item);
			// 元素后移
			cur = cur.next;
		}

		// 遍历输出
		while (stack.size() > 0) {
			System.out.println(stack.pop());
		}
	}

本文地址：https://blog.csdn.net/qq_40889383/article/details/107476678