JAVA数据结构与算法的学习——单链表的实现

深碍√TFBOYSˉ_ 2022-03-10 01:22 181阅读 0赞

今天用**JAVA**实现数据结构中的**单链表**，思路就不重复了，大家仔细品味代码。  
第一步，在包里建立**LinkList类**，用于**定义链表**和一下**操作链表的方法**  
**LinkList类**：

public class  LinkList {
    	public Node head; //头引用
    	public Node rear; //尾引用
    	public Node point;//临时引用
    	public int length;//链表长度
    	//链表的构造函数，创建无数据的头节点
    	public LinkList() {
    		head = new Node();
    		rear = head;
    		length = 0;
    	}
    	//从尾部插入链表
    	public void add(int data) {
    		point =new Node(data);
    		rear.next = point;
    		rear = point;
    		length++;
    	}
    	//在指定位置插入元素成为第p个元素
    	public void insert(int position,int data) {
    		Node tmp = new Node(data);
    		if(position>0 && position<=length) {
    			int i =1;
    			point = head;
    			//查找到第position-1位的元素，将引用point指向它
    			while(i<position && length!=0) {
    				point = point.next;
    				i++;
    			}
    			tmp.next = point.next;
    			point.next = tmp;
    			length++;
    		}else {
    			System.out.println("没有指定位置，插入失败");
    		}
    	}
    	//打印链表
    	public void printList() {
    		point = head;
    		if(head != null) {
    			System.out.print("["+ head.data +"]");
    		}
    		while(point.next !=null) {
    			System.out.print("→["+ point.next.data +"]");
    			point = point.next;
    		}
    		System.out.println();
    	}
    	//获得链表的长度
    	public int getLength() {
    		return length;
    	}
    	//查找指定位置元素
    	public Object find(int position) {
    		if(position >=0 && position <=length) {
    			int i=1;
    			point = head;
    			while(i<=position) {
    				point = point.next;
    				i++;
    			}
    			return point.data;
    		}else {
    			System.out.println("查找失败，没有指定位置的元素");
    			return null;
    		}
    	}
    	//删除指定位置元素
    	public void remove(int position) {
    		if(position >=0 && position <length) {
    			int i =1;
    			point = head;
    			//查找到第position-1位的元素，将引用point指向它
    			while(i<position && length!=0) {
    				point = point.next;
    				i++;
    			}
    			Node tmp = point.next;
    			point.next = tmp.next;
    			length--;
    		}else {
    			System.out.println("删除失败，没有指定位置的元素");
    		}	
    	}
    	//修改指定位置的元素
    	public void set(int position,int data) {
    		if(position>0 && position<=length) {
    			int i=1;
    			point = head;
    			while(i<=position) {
    				point = point.next;
    				i++;
    			}
    			point.data = data;
    		}else {
    			System.out.println("修改失败，没有指定位置的元素");
    		}
    	}
    	//查找元素的值，返回下标
    	public Object search(int data) {
    		point = head.next;
    		int i=1;
    		while(point != null) {
    			if(point.data.equals(data)) {
    				break;
    			}
    			i++;
    			point = point.next;
    		}
    		if(i>length) {
    			System.out.println("没有找到该元素");
    			return null;
    		}
    		return i;
    	}
    	//清空链表(java垃圾回收，当对象没有引用指向)
    	public void clear() {
    		while(head.next !=null) {
    			head.next = head.next.next;
    		}
    		rear = head;
    		point = null;
    		length = 0;
    		System.gc();
    	}
    }

第二步，在包里建立**Node类**，用于**定义节点**，**数据域和所谓的指针域**  
**Node类：**

public class Node {
    	protected Object data;
    	protected Node next=null;
    	
    	public Node() {
    		data = null;
    	}
    	public Node(int data) {
    		this.data=data;
    	}
    }

最后就是简单的测试了，对每个方法进行测试并输出结果，检验是否有异常

public class Test {
    
    	public static void main(String[] args) {
    		LinkList L = new LinkList();
    		L.add(1);
    		L.add(2);
    		L.add(3);
    		L.printList();
    		System.out.println(L.getLength());
    		System.out.println(L.find(3));
    		L.insert(3, 4);
    		L.printList();
    		L.set(3, 3);
    		L.printList();
    		L.set(4, 4);
    		L.printList();
    		L.remove(2);
    		L.printList();
    		System.out.println(L.search(2));
    		L.clear();
    		L.printList();
    		L.add(1);
    		L.add(2);
    		L.add(3);
    		L.printList();
    	}
    
    }

**测试结果**：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70][]  
**不对之处还请各位不吝赐教**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwNDMyMw_size_16_color_FFFFFF_t_70]: /images/20220310/835d1b4ff1bb41caa47e86fe5e3df1b9.png