Java实现单向单链表

朱雀 2023-07-08 09:17 131阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

实现起来要比静态链表简单很多，指针就是方便。

public class SingleList<T> {
        
    	//头节点，不保存数据
    	private Node head;
    	private int len;
    	private class Node {
        
    		Node next = null;
    		T data;
    		public Node(T t) {
        
    			this.data = t;
    		}
    	}
    	 public SingleList() {
        
    		 this.head = new Node(null);
    		 this.len = 0;
    	 }
    	//向链表尾部加入节点
    	 public void addTail(T t) {
        
    		 Node temp = head;
    		 while(temp.next != null){
        
    			 temp = temp.next;
    		 }
    		 temp.next = new Node(t);
    		 this.len++;
    	 }
    	 //向链表指定位置后面插入节点
    	 public void insert(T t, int index) {
        
    		 if(index<0 || index>len) {
        
    			 throw new ArrayIndexOutOfBoundsException("Index error");
    		 }
    		 Node temp = head;
    		 for(int i=0;i<index;i++) {
        
    			 temp = temp.next;
    		 }
    		 Node node =new Node(t);
    		 node.next = temp.next;
    		 temp.next = node;
    		 this.len++;
    	 }
    	 //查找链表中是否存在某个数据,如果有返回第一个与其数据相等的节点的位置，没有返回0
    	 public int find(T t) {
        
    		 int count = 1;
    		 Node temp = head.next;
    		 while(temp != null) {
        
    			 if(temp.data.equals(t)) {
        
    				 return count;
    			 }
    			 count++;
    			 temp = temp.next;
    		 }
    		 return 0;
    	 }
    	 //删除指定位置的节点
    	 public T delete(int index) {
        
    		 if(index<1 || index>len) {
        
    			 throw new ArrayIndexOutOfBoundsException("Index error");
    		 }
    		 Node temp = head;
    		 //找到要删除位置的前一个节点
    		 for(int i=1;i<index;i++) {
        
    			 temp = temp.next;
    		 }
    		 T t = temp.next.data;
    		 temp.next =temp.next.next;
    		 this.len--;
    		 return t;
    	 }
    	 //返回链表指定位置的值
    	 public T findIndex(int index) {
        
    		 if(index<1 || index>len) {
        
    			 throw new ArrayIndexOutOfBoundsException("Index error");
    		 }
    		 Node temp = head;
    		 for(int i=0;i<index;i++) {
        
    			 temp = temp.next;
    		 }
    		 return temp.data;
    	 }
    	 //输出链表
    	 public void printList() {
        
    		 Node temp = head.next;
    		 while(temp != null) {
        
    			 System.out.print(temp.data + " ");
    			 temp = temp.next;
    		 }
    		 System.out.print(" " + len + "\n");
    	 }
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method 
    		SingleList<Character> sl = new SingleList<Character>();
    		sl.addTail('a');
    		sl.addTail('c');
    		sl.printList();
    		sl.insert('b', 1);
    		sl.addTail('d');
    		System.out.println(sl.findIndex(5));
    		sl.printList();
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982