链表----单项链表

 

/**
 * 单项连接表
 */

package com.szy.structure.list;

import java.util.Scanner;

class Node
{
	public int id;  //节点的ID编号，作为主键使用，有用户指定
	public Node next;
}
public class SinglyLinkedList
{
	private Node START;
	
	public SinglyLinkedList()
	{
		START=null;
	}
	
	/**
	 * 插入节点方法，根据用户输入的ID值遍历链表，把新的
	 * 节点插入的指定位置。要排序的。
	 */
	public void addNode()
	{
		System.out.println("Input node info:");
		Scanner scanner=new Scanner(System.in);
		int nodeId=scanner.nextInt();
		//创建一个新的节点
		Node newNode=new Node();
		newNode.id=nodeId;
		newNode.next=null;
		
		//如果插入的节点是第一个节点
		if ((null==START)||(nodeId<=START.id))
		{
			if ((null!=START)&&(nodeId==START.id))
			{
				System.out.println("\nDuplicate id.");
				return;
			}
			newNode.next=START;
			START=newNode;
			return;
		}
		//遍历链表找到新的插入位置
		Node pre,curr;
		pre=START;
		curr=START;
		while((curr!=null)&&(nodeId>=curr.id))
		{
			if (curr.id==nodeId)
			{
				System.out.println("\nDuplicate id.");
				return;
			}
			pre=curr;
			curr=curr.next;
		}
		pre.next=newNode;
		newNode.next=curr;
	}
	
	/**
	 * 删除指定节点
	 * @param 节点ID
	 */
	public boolean delNode(int id)
	{
		Node pre=START;
		Node current=START;
		while(current!=null)
		{
			if (current.id==id)
			{
				if (current.equals(START))
				{
					START=START.next;
				}
				else
				{
					pre.next=current.next;
				}
				return true;
			}
			pre=current;
			current=current.next;
		}
		return false;
	}
	/**
	 * 查找节点
	 * @param 节点ID
	 * @return
	 */
	public boolean searchNode(int id )
	{
		Node current=START;
		while(current!=null)
		{
			if (current.id==id)
			{
				return true;
			}
			current=current.next;
		}
		return false;
	}
	/**
	 * 循环遍历链表
	 */
	public void traverse()
	{
		if (listEmpty())
		{
			System.out.println("The list is Empty");
		}
		else
		{
			System.out.println("The records in the list are:");
			Node current=START;
			while(current!=null)
			{
				System.out.print(current.id+"-->");
				current=current.next;
			}
		}
	}
	/**
	 * 判断链表是否为空
	 * @return
	 */
	public boolean listEmpty()
	{
		if (START==null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	public static void main(String[] args)
	{
		SinglyLinkedList list=new SinglyLinkedList();
		while(true)
		{
			System.out.println("\n------------------------------------");
			System.out.println("Menu：");
			System.out.println("1.Add a record to the list");
			System.out.println("2.Delete a record from the list");
			System.out.println("3.View all the records in the list");
			System.out.println("4.Search for a record in the list");
			System.out.println("5.Exit");
			System.out.println("------------------------------------");
			System.out.println("Enter you choice:");
			Scanner scanner=new Scanner(System.in);
			int select=scanner.nextInt();
			switch (select)
			{
			case 1:
				list.addNode();
				break;
			case 2:
			{
				if (list.listEmpty())
				{
					System.out.println("List is empty");
					break;
				}
				System.out.println("\nInput the id of the list:");
				int id=scanner.nextInt();
				if (list.delNode(id))
				{
					System.out.println("Delete success！");
				}
				else
				{
					System.out.println("This id node is not exit!");
				}
			}
			break;
			case 3:
			{
				list.traverse();
			}
			break;
			case 4:
			{
				if (list.listEmpty())
				{
					System.out.println("List is empty");
					break;
				}
				else
				{
					System.out.println("\nInput the id of the list:");
					int id=scanner.nextInt();
					if (list.searchNode(id))
					{
						System.out.println("Record found!");
					}
					else
					{
						System.out.println("Record not found");
					}
				}
			}
			break;
			case 5:return;
			default:
				break;
			}
		}
	}
}