java实现链表，实现常用的操作

男娘i 2022-05-15 01:14 125阅读 0赞

在之前的学习过程中用C++实现过各种常见的数据结构。今天用java实现了一个链表，并包含了常用的操作。欢迎大家指正。

import java.util.Scanner;
    
    import javax.lang.model.element.Element;
    
    
    public class LinkList<E>{
    
    	private Node<E> headNode; //头结点
    	private Node<E> tailNode; //尾节点
    	private int size=0;  //大小
    	class Node<E> {
    		public E data;  //节点数据
    		public Node<E> next;  //节点的下一个节点
    
    		//链表节点构造函数
    		public  Node(E data,Node<E> next) { 
    			this.data=data;
    			this.next=next;
    		}
    	}
    
    	/**
    	 * 初始化一个一个空链表
    	 */
    	public LinkList() {
    		headNode=null;
    		tailNode=null;
    	}
    
    	/**
    	 * 创建一个头结点的链表
    	 * @param data 数据
    	 */
    	public LinkList(E data) {
    		headNode=new Node(data,null);
    		tailNode=headNode;
    		size++; //长度加1
    	}
    	/**
    	 * 返回链表长度
    	 * @return
    	 */
    	public int lengeth() {
    		return size;
    	}
    
    	/**
    	 * 通过索引找节点
    	 * @param index 索引
    	 * @return 返回找到的节点
    	 */
    	public Node findByByIndex(int index) {
    		if (index<0||index>size-1) { //越界判断
    			throw new IndexOutOfBoundsException("线性表索引越界");
    		}
    		Node current=headNode; 
    		//循环查找
    		for (int i = 0; i < size && current.next!=null; i++,current=current.next) {
    			if (i==index) {
    				return current;
    			}
    		}
    		return null;
    
    	}
    
    	/**
    	 * 通过值查找
    	 * @param element 待查找的值
    	 * @return 返回索引
    	 */
    	public int findByElement(E element) {
    		Node current =headNode; 
    		//遍历查找节点值相等的
    		for (int i = 0; i < size-1 && current.next!=null; i++,current=current.next) {
    			if (current.data==element) {
    				return i;
    			}
    		}
    		return -1; //未找到的情况
    	}
    
    	/**
    	 * 插入
    	 * @param index 待插入位置
    	 * @param element 插入的值
    	 */
    	public void insert(int index,E element){
    		if (index<0||index>size-1) {
    			throw new IndexOutOfBoundsException("线性表索引越界");
    		}
    		if (headNode==null) { //空链表时
    			addAtTail(element); //直接在尾部添加
    		}else { 
    			if (index==0) { //第一位插入
    				addAtHead(element);
    			}else {
    				Node prv=findByByIndex(index-1);//查找待插入节点的前一位  
    				prv.next=new Node<E>(element, prv.next); //插入
    				size++; //链表大小加1
    			}
    		}
    	}
    
    	/**
    	 * 在尾部添加
    	 * @param element 值
    	 */
    	public void addAtTail(E element) {
    		if (headNode==null) { //空链表事
    			headNode=new Node<E>(element, null); //头节点指向新建的待插入的节点
    			tailNode=headNode; //尾指针指向头结点
    		}else{
    			Node newNode = new Node<E>(element, null); //新建一个待插入的节点
    			tailNode.next=newNode; //添加到尾部
    			tailNode=newNode;//尾节点指向新建的节点
    		}
    	}
    
    	/**
    	 * 在头部添加
    	 * @param element
    	 */
    	public void addAtHead(E element) {
    		headNode = new Node<E>(element, headNode);
    		if (tailNode==null) { //空链表时
    			tailNode=headNode;
    		}
    	}
    
    	/**
    	 * 删除节点
    	 * @param index 待删除的下标
    	 * @return 被删除的值
    	 */
    	public E delete(int index) {
    		Node deleteNode = null;
    		if (index<0 || index>size-1) {  
    			throw new IndexOutOfBoundsException("数组越界");
    		}
    		if (index==0) { //删除头结点
    			deleteNode=headNode;
    			headNode=headNode.next;
    		}else {
    			Node preN=findByByIndex(index-1); //得到删除节点的前一个节点
    			deleteNode=preN.next; //要删除的节点就是prev的next指向的节点
    			preN.next=deleteNode.next; //删除以后prev的next指向被删除节点之前所指向的next
    			deleteNode.next=null;//
    		}
    		size--;
    		return (E) deleteNode.data;
    
    	}
    	//删除链表中最后一个元素
    	public E removeLast() {
    		size--;
    		return delete(size-1);
    	}
    	//清除链表中所有的元素
    	public void clear() {
    		headNode=null;
    		tailNode=null;
    		size=0;
    	}
    	//判断链表是否为空
    	public boolean isEmpty() {
    		return size==0;
    	}
    	//更改某节点的值
    	public void set(int index,E element) {
    		if (index>=0 && index<size) {
    			Node node = findByByIndex(index);//找到这个节点
    			node.data=element;
    		}
    	}
    	//遍历输出链表
    	public void traverse() {
    		Node node =headNode;
    		if (headNode!=null) {
    			System.out.print("[" + headNode.data + "]");
    		}
    		while (node.next!=null) {
    			System.out.print("[" + node.next.data + "]");	
    			node=node.next;
    		}
    	}
    	/**
    	 * 寻找链表的倒数的第k位
    	 * @param k 位数
    	 * @return 
    	 */
    	public E lastFind(int k) {
    		Node first = headNode;
    		Node second=null;
    		for (int i = 0; i < k-1; i++) { //第一个节点先走k-1位
    			if (first.next!=null) {
    				first=first.next;
    			}
    		}
    		second=headNode;  //第二个节点指向头结点
    		while (first.next!=null) { //两个指针一起向后移动，直到第一个节点指向了尾节点，就找到了
    			first=first.next;
    			second=second.next;
    		}
    		return (E) second.data;	
    
    	}
    
    	/**
    	 * 反转链表
    	 * @param headNode 头结点
    	 * @return 返回头结点
    	 */
    	public Node reverseList(Node headNode) {
    		Node reverseHead=null; //反转后的头结点
    		Node pNode=headNode;   //当前节点
    		Node preNode=null;     //当前节点的亲一个节点
    		if (headNode==null) {
    			return null;
    		}
    		if (headNode.next==null) {
    			return headNode;
    		}else {
    			while (pNode!=null) {
    				if (pNode.next==null) {//反转完毕
    					reverseHead=pNode;
    				}
    				pNode.next=preNode; //当前指向前一个节点
    				preNode=pNode;      
    				pNode=pNode.next;   //开始反转下一个
    
    			}
    		}
    		return reverseHead;
    	}
    
    	/**
    	 * 合并两个有序的递增链表
    	 * @param head1
    	 * @param head2
    	 * @return 合并后的头结点
    	 */
    	public  Node Merge(Node head1, Node head2) {
    		if (head1 == null) {
    			return head2;
    		}
    		if (head2 == null) {
    			return head1;
    		}
    		Node mergeNode = null;
    		
    //		if (head1.data < head2.data) { //假设data为int
    //			mergeNode = head1;
    //			mergeNode.next = Merge(head1.next, head2);//下一个节点是哪一个得递归判断
    //		} else {
    //			mergeNode = head2;
    //			mergeNode.next = Merge(head1, head2.next);//下一个节点是哪一个得递归判断
    //		}
    		return mergeNode;
    	}
    
    	public String toString() {
    		if (headNode==null) {
    			return "[]";
    		}
    		StringBuilder strBuilder=new StringBuilder();
    		for (Node current=headNode;current!=null;current=current.next) {
    			strBuilder.append(current.data.toString()+",");
    		}
    		int len = strBuilder.length();
    		return strBuilder.delete(len-1, len).append("]").toString();
    	}
    
    
    }