Java 实现单向链表（Single-Linked List）+测试

• 链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

• 优点：使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
• 缺点：链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。

下面实践单链表。

功能包含：

1. 初始化单链表
2. 在链表头添加节点
3. 在链表头删除节点
4. 查找指定元素，找到了返回节点Node，找不到返回null
5. 在任意位置插入一个元素。（注：头结点位置，pos=1.）
6. 删除指定的元素，删除成功返回true
7. 判断链表是否为空
8. 打印链表信息

package datastructure;

public class SingleLinkedList {
	private int size;//链表节点的个数
	private Node head;//头结点
	
	public SingleLinkedList() {
		size = 0;
		head = null;
	}
	
	//链表每个节点类
	private class Node{
		//每个节点的数据，Object是所有Java类的父类。目的是使编写的程序有更大的通用性，例如这里的data可以接收任意类型的数据。
		private Object data;
		private Node next;//每个节点指向下一个节点的连接(这里的next本质也是Node类型，因为next指向的确实是一个节点)
		public Node(Object data) {
			this.data = data;
		}
	}
	
	//在链表头添加元素
	public Object addHead(Object obj) {
		Node newHead = new Node(obj);
		//如果当前链表节点个数为0，那么newHead节点就是头结点。
		if(size == 0) {
			head = newHead;
		//否则将新添加的这个节点指向原始头结点，新节点自己作为头结点。
		}else {
			newHead.next = head;
			head = newHead;
		}
		//链表节点个数记得要更新
		size++;
		return obj;
	}
	
	//在链表头删除元素
	public Object deleteHead() {
		Object obj = head.data;
		head = head.next;
		size--;
		return obj;
	}
	
	//查找指定元素，找到了返回节点Node，找不到返回null
	public Node find(Object obj) {
		Node current = head;
		int tempSize = size;
		while(tempSize>0) {
			if(obj.equals(current.data)) {
				return current;
			}else {
				current = current.next;
			}
			tempSize--;
		}
		return null;
	}
	
	//插入一个元素，注：头结点位置，pos=1.
	public boolean insert(int pos, Object value) {
		if(size == 0) {
			return false;
		}
		//如果是插在链表的头结点之前，那么相当于是一个addHead()操作
		if(pos == 0) {
			addHead(value);
			//要及时更新链表长度，不然在display()打印的方法里会打印不完全。
			size++;
			return true;
		}
		//在链表末尾插入一个节点
		else if (pos == size) {
			Node current = head;
			while(current.next!=null) {
				current = current.next;
			}
			Node insert_node = new Node(value);
			
			current.next = insert_node;
			//及时更新链表长度
			size++;
			return true;
			
		}
		//其他位置插入
		else {
			Node current = head;
			//1System.out.println(current.data);
			Node insert_node = new Node(value);
			int count = 1;
			//从头结点开始遍历，找到pos位置就退出，直到达到链表的末尾
			while(current.next != null) {
				
				
				if(count == pos) {
					Node temp;
					//保存插入点的前一个元素的next节点信息到temp
					temp = current.next;
					//插入点的前一个元素的next节点更新为insert_node
					current.next = insert_node;
					//insert_node的next，为之前保存的temp结点
					insert_node.next = temp;
					size ++ ;
					return true;
				}
				count += 1;
				current = current.next;
				
			}
			return false;	
		}
	}
	

	//删除指定的元素，删除成功返回true
	public boolean delete(Object value) {
		if(size == 0) {
			return false;
		}
		Node current = head;
		Node previous = head;
		while(current.data != value) {
			if(current.next == null) {
				return false;
			}else {
				previous = current;
				current = current.next;
			}
		}
		//如果删除的是第一个节点
		if(current == head) {
			head = current.next;
			size--;
		}else {
			//如果删除的不是首节点，更改链接关系
			previous.next = current.next;
			size--;
		}
		return true;
	}
	
	//判断链表是否为空
	public boolean isEmpty() {
		/*if(size == 0) {
			return true;
		}
		return false;
	}*/	
		return (size == 0);
	}
	
	//显示链表信息
	public void display() {
		if(size>0) {
			Node node = head;
			int tempSize = size;
			if(tempSize == 1) {
				System.out.print("["+node.data+"]");
				return;
			}
			
			while(tempSize>0) {
				if(node.equals(head)) {
					System.out.print("["+node.data+"->");
				}else if(node.next == null) {
					System.out.print(node.data+"]");
				}else {
					System.out.print(node.data+"->");
				}
				node = node.next;
				tempSize--;
			}
			System.out.println();
		}else {//链表一个节点也没有
			System.out.println("[]");
		}
	}
	
	public void testSingleLinkedList(){
	    SingleLinkedList singleList = new SingleLinkedList();
	    //添加节点
	    singleList.addHead(1);
	    singleList.addHead(2);
	    singleList.addHead(3);
	    singleList.addHead(4);
	    singleList.addHead(5);
	    //打印当前链表信息
	    System.out.println("打印当前链表信息");
	    singleList.display();
	    //2号节点位置插入元素6
	    System.out.println("2号节点位置插入元素6");
	    singleList.insert(2, 6);
	    singleList.display();
	    //删除元素6
	    System.out.println("删除元素6");
	    singleList.delete(6);
	    singleList.display();
	    //查找元素3
	    System.out.println("查找元素3");
	    System.out.println(singleList.find(3));

	}
	
	
	public static void main(String[] args) {
		SingleLinkedList L = new SingleLinkedList();

		L.testSingleLinkedList();
		
		
	}
}

测试结果：


参照一篇博客写的，因为java基础还不太熟，写的比较糙，后续回头看的时候再优化吧。