[数据结构与算法]单向链表—— Java实现

package com.muluo.linkedList;

public class SingleLinkedList<E> {

	public class Node<E> {
		public E e;
		public Node next;

		public Node(E e, Node next) {
			super();
			this.e = e;
			this.next = next;
		}

		public Node(E e) {
			this(e, null);
		}

		public Node() {
			this(null, null);
		}

		@Override
		public String toString() {
			return this.e + "";
		}
	}

	private Node dummyHead;
	private int size;

	public SingleLinkedList() {
//		head = null;
		dummyHead = new Node(null, null);
		size = 0;
	}

	public void reverse() {
		Node cur = dummyHead.next;
//		将第二个元素放到第一个元素的后面
		Node next = cur.next;

		Node reverseNode = new Node();
		while (cur != null) {
			next = cur.next;
			cur.next = reverseNode.next;
			reverseNode.next = cur;
			cur = next;
		}
		dummyHead = reverseNode;
	}

	/**
	 * 获取链表的长度
	 * 
	 * @return
	 */
	public int getSize() {
		return size;
	}

	/**
	 * 返回移除的元素
	 * 
	 * @param index
	 * @return
	 */
	public E remove(int index) {
		if (index < 0 || index > size) {
			System.out.println("添加失败，下标违规");
		}
		Node prev = dummyHead;
		// 先找到要删除的前一个结点
		for (int i = 0; i < index; i++) {
			prev = prev.next;
		}
		Node retNode = prev.next;
		prev.next = retNode.next;
		retNode.next = null;
		size--;
		return (E) retNode.e;
	}

	/**
	 * 移除链表最后一个元素
	 * 
	 * @return
	 */
	public E removeLast() {
		return remove(size - 1);
	}

	/**
	 * 移除第一个元素并返回
	 */
	public E removeFirst() {
		return remove(0);
	}

	/**
	 * 判断某个元素是否在链表中
	 * 
	 * @param num
	 * @return
	 */
	public boolean contains(E e) {
		Node cur = dummyHead;
		while (cur.next != null) {
			if (cur.e == e) {
				return true;
			}
			cur = cur.next;
		}
		return false;
	}

	/**
	 * 判断是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	public void addFirst(E e) {
//		Node node = new Node(num);
//		node.next = head;
//		head = node;
//		size++;
		add(0, e);
	}

	/**
	 * 任意位置添加
	 * 
	 * @param index
	 * @param num
	 */
	public void add(int index, E e) {
		if (index < 0 || index > size) {
			System.out.println("添加失败，下标违规");
		}

		// 头结点为空，则可以创建一个虚拟头结点

//		if (index == 0) {
//			addFirst(num);
//		} else {
		Node prev = dummyHead;
		for (int i = 0; i < index; i++) {
			prev = prev.next;
		}

//			Node node = new Node(num);
//			node.next = prev.next;
//			prev.next = node;
		prev.next = new Node(e, prev.next);
		size++;
//		}
	}

	/**
	 * 尾部添加元素
	 * 
	 * @param num
	 */
	public void addLast(E e) {
		add(size, e);
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		Node cur = dummyHead.next;
		while (cur != null) {
			builder.append(cur + "->");
			cur = cur.next;
		}
		builder.append("NULL");
		return builder.toString();
	}
}

主测试类

package com.muluo.linkedList;

public class MainSingleLinkedLista {
	public static void main(String[] args) {
		SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();
		singleLinkedList.addFirst(1);
		singleLinkedList.addLast(2);
		singleLinkedList.addLast(3);
		singleLinkedList.addLast(4);

		System.out.println(singleLinkedList.toString());
		singleLinkedList.add(2, 6);
		System.out.println(singleLinkedList.toString());

		System.out.println(singleLinkedList.contains(3));
		System.out.println(singleLinkedList.toString());

		System.out.println(singleLinkedList.remove(2));
		System.out.println(singleLinkedList.toString());

		System.out.println(singleLinkedList.removeFirst());
		System.out.println(singleLinkedList.toString());

		System.out.println(singleLinkedList.removeLast());
		System.out.println(singleLinkedList.toString());

		System.out.println("===反转===");
		singleLinkedList.reverse();
		System.out.println(singleLinkedList.toString());
	}
}