java 实现链表（自己写的）

今天用java写了下的链表， 还是有点糊涂的。这和C语言写的链表还是有点不太一样的。感觉C语言的结构清晰点的，可能是内存中保存的值是引用还是真的值有关系吧有两点要说明下的：

1、Head --> Node --> Node --> Node --> Node

     链表的head是不保存数据的，一般开辟内存然后在里面放null空对象。保存值从第一个Node开始的。C语言好像也是这样的吧

2. 下面的程序我到是测试了下，平时过过面试笔试的关是没有问题了。但是有的地方还是需要再分析下的。

实现了增加删除显示

下面是步骤

 

创建People类，这个就相当于我们放入到链表中的数据

package endual;

public class People {

	private int id ;
	private String name ;
	private int age ;
	
	public People(int id, String name, int age) {
		super();
		this.id = id;
		this.name = name;
		this.age = age;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getAge() {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}
	
	
	
	
	
}

 

步骤二：创建Node节点

 

package endual;

public class Node {



	private People people = new People(0,"head",0);
	private Node nextNode ;
	
	public Node(People people,Node nextNode) {
		super();
		this.people = people ;
		this.nextNode = nextNode ;
	}
	
	//显示该节点的数据
	public void display() {
		
		System.out.println(people.getId() +"--" +
		                   people.getName() +"--" +
				           people.getAge()) ;
		
	}
	
	public People getPeople() {
		return people;
	}

	public void setPeople(People people) {
		this.people = people;
	}

	public Node getNextNode() {
		return nextNode;
	}

	public void setNextNode(Node nextNode) {
		this.nextNode = nextNode;
	}
	
	
	
}

 

需要说明的是一个节点，中是保护一个数值和下一个节点

 

步骤三：

 

链表的实现

 

package endual;



/**
 * 最重要的说明，head节点是不保存people数据的只是一个头节点，保存数据是从head的下一个节点开始的
 * @author Endual
 *
 */
public class LinkList {
	
	//链表的头节点是很重要的,寻找到头节点就能做删除插入等操作了
	
	private Node head  ; 
	private int nItems = 0 ; //链表的数据个数有多少个,初始化是0
	
	public LinkList() {
		
		this.head = new Node(null,null) ; //这里必须开辟对象，将head指向一个对象
	}
	
	//判断是否为空
	public boolean isEmply() {
		
		if(this.nItems==0) {
			return true ;
		}
		return false ;
		
	}
	

	// * 链表的长度

	public int size() {
		
		return this.nItems ;
		
	}
	
	//插入一个node到链表的尾部                                                                                               

	public void insertTail(People people) { //传递进来的就是新的node 
	   // Head(头节点的数据是没有的) --> Node（保存数据从这里开始） --> Node --> Node --> FirstNode
	   // 相当于Node node = new Node(new People) ;
		Node node = new Node(people,null) ; //创建一个新的Node的链表节点，其中数据是传入进来的people,下一个节点是null
		
		Node temp = head ; //创建了一个中间变量，中间变量的变化就是head的变化
		
		while (null != temp.getNextNode()) {
			
			temp = temp.getNextNode() ;
			
		}
		
		temp.setNextNode(node) ; //一般而言是从第二个节点才开始放数据的，所以头节点是的node是NULL
		this.nItems++ ;
		
         
       
	}
	
	//插入一个node到一个链表的头部
	public void insertHead(People people) { //将新插入的node节点作为第一个显示的节点
		
		Node node = new Node(people,null) ; //将要被插入的节点
	
      	node.setNextNode(head.getNextNode()) ; //插入节点的下一个节点是head指向的下一个节点
      	
      	head.setNextNode(node) ; //head指向的下一个节点改变成为node
        
        this.nItems++ ; //插入数据将存放的个数加1；
		
	}
	
	//根据标号来插入数据 从0开始 
	
	public void insert(int index, People people) {
		
		//判断插入的数据是否合法
		if(index < 0 || index > this.nItems) {
			System.out.println("插入的index错误") ;
			return ;
		}
		Node node = new Node(people,null) ; //将要被插入的节点
		Node temp = head ;
		for (int i=0; i < index; i++) {
			temp = temp.getNextNode() ; //这个就是第index个节点的前一个节点，查在这个位子，这个位子要向
		}
		node.setNextNode(temp.getNextNode()) ;
		temp.setNextNode(node) ;
		this.nItems++ ;
	}
	
	//根据位子来查找数据
	
	public People find(int index) {
	
		if (index < 0 ) {
			
			System.out.println("查找的index位子不能小于0");
			return null;
			
		}
		
		if (index+1 > this.nItems) {
			
			System.out.println("查找的位子大于链表的长度了");
			return null;
			
		}
		
		
		Node temp = head ;
		for (int i=0; i <= index; i++) {
			
			temp = temp.getNextNode() ;
			
		}
		
		return temp.getPeople();
		
	}
	
	//根据位子删除
	public void delete(int index) {
		
        if (index<0 || index > this.nItems) {
        	
        	System.out.println("index数据或大或小");
        	return ;
        	
        }
        
        /**
         * 说明
         * index = 0 , 删掉第一个,找到head
         * index = 1 , 删掉第二个,找到第一个
         * index = 2 ， 删掉第三个,找到第二个
         */
        
		Node temp = head ;
		for (int i=0; i < index; i++) {
			
			temp = temp.getNextNode() ;
		}
		
		temp.setNextNode(temp.getNextNode().getNextNode()) ;
		this.nItems-- ;
		
		
	}
	//删除结尾
	public void delectTail() {
		
		if(this.nItems==0) {
			
			System.out.println("当前链表为空") ;
			return ;
			
		}
		Node temp = head ;
		for (int i=0; i < this.nItems-1; i++) {
			temp = temp.getNextNode() ;
		}
		temp.setNextNode(null) ;
		this.nItems-- ;
	}
	
	
	//删除头
	public void deleteHead(){
       
		if(this.nItems==0) {
			System.out.println("当前链表为空") ;
			return ;
		}
		
		Node temp = head ;
		head.setNextNode(temp.getNextNode().getNextNode()) ;
		this.nItems-- ;
		
	}
	
	/**
	 * 显示链表
	 */
	public void display() {
		

		Node current = head ;
		
		if (this.nItems == 0) {
			System.out.println("当前链表为空") ;
			return ;
		}
		//while中用node节点的下一个节点是否为空
		while (current.getNextNode() != null) { //在while中如果第一次是null那么说明是这个链表还没有数据
			
			current = current.getNextNode() ; //将当前节点移动到下一个节点
			current.display() ; //显示当前节点
		}
		
		
	}
	
	
}

 

步骤四 ：测试类的实现

 

package endual;

public class Mian {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		People p1 = new People(1, "n1", 1) ;
		People p2 = new People(2, "n2", 2) ;
		People p3 = new People(3, "n3", 3) ;
		People p4 = new People(4, "n4", 4) ;
		People p5 = new People(5, "n5", 5) ;
		People p6 = new People(6, "n6", 6) ;
		People p7 = new People(7, "n7", 7) ;
		
		LinkList lk = new LinkList() ;
		lk.display() ;
	
		lk.insertTail(p1) ;
		lk.insertTail(p2) ;    
		lk.insertTail(p3) ;
		lk.insertTail(p4) ;
		lk.insertTail(p5) ;
		lk.insertTail(p6) ;
		lk.insertTail(p7) ;
		lk.display() ;
		
//		System.out.println(lk.find(0).getId()) ;
//		System.out.println(lk.find(1).getId()) ;
//		System.out.println(lk.find(2).getId()) ;
//		System.out.println(lk.find(3).getId()) ;
//		System.out.println(lk.find(4).getId()) ;
//		System.out.println(lk.find(5).getId()) ;
//		System.out.println(lk.find(6).getId()) ;
//		System.out.println(lk.find(7).getId()) ;
		
		lk.delete(0) ;lk.delete(3) ;
		lk.display() ;
		
		
	}

}

 需要说明的是 测试类可以自己写 。

 

希望对面试啊 笔试啊 有好处吧。

 

我非常愿意与你交流关于面试笔试已经学习基础的数据结构和算法的问题。因为本人现在在复习这个。

我的QQ:1019990976 麻烦注明：数据结构