【数据结构】(链表的Java实现与经典应用)

链表作为数据结构的基石,它的出现给很多的方法提供了优化措施,链表是最重要的数据结构之一,在我心里,链表就是数据结构的灵魂，本篇利用数组和内部类两种方式实现了链表的定义和基本方法的实现,当然我最爱内部类的实现形式( `)3’)▃▃▃▅▆▇▉

前言

对于Java实现链表将Node作为内部类是个很好的选择，所以这里给出两个Java实现链表的版本，个人比较认同第二种。因为在链表的添加顺序是由右向左，先添加的节点对下一节点的引用可以为空，并且引用是引用下一节点而不是下一节点的对象，因为具有连续引用使得头节点可以操作所有节点，所以需要一个头节点和视情况而定的若干临时节点

链表的Java实现

第一种

package SqueneList;

public class Sqlist {

	private static int MAXSIZE;
	private static int[] sqlist;
	private static int length;
	//用最大数组长度来初始化顺序表
	public Sqlist(int MAXSIZE){
		this.sqlist = new int[MAXSIZE];
		this.MAXSIZE=MAXSIZE;
		this.length=0;
	}
	//用数组来初始化顺序表
	public Sqlist(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			sqlist[i] = arr[i];
		}
		this.length = arr.length;
	}
	//对由数组实现的顺序表进行扩充
	public void expandList(){
	    int[] newarr = new int[arr.length*2]
	    for(int i=0;i<arr.length;i++){
	        newarr[i]=arr[i]
	    }
	    arr = newarr;
	}
	//向顺序表指定位置插入元素
	public int listInsert(int i, int e) 
	{
		if(i<1) {
			System.out.println("非法插入位置");
			return -1;
		}else if(this.length == this.MAXSIZE) {
			System.out.println("顺序表已满");
			return -2;
		}
		for(int k=length-1;k>=i-1;k--) {
			sqlist[k+1]=sqlist[k];  //数组中插入位置及其后的元素均向后移动一位
		}
		sqlist[i-1]=e;  //将制定元素插入此位置
		this.length++;  //插入后的顺序表长度+1
		return 0;
	}
	//清空顺序表
	public void listClear() {
		this.length = 0;  //仅用来判断是否为空，直接将长度设置为0
	}
	//判断顺序表是否为空
	public boolean isEmpty() {
		return this.length==0;
	}
	//获取指定位置的顺序表元素
	public static int getElem(int i) {
		if(i<1||i>length)
		{
			System.out.println("获取位置不合法");
			return -1;
		}
		return sqlist[i-1];
		
	}
	//获取制定元素的位置信息
	public int getIndex(int e, int i) {
		for(int j=0;j<=length-1;j++)
		{
			if(sqlist[j]==e) {
				i=j++;
				return i;
			}
		}
		System.out.println("顺序表中无对应元素");
		return 0;
	}
	//打印顺序表
	public static void printList() {
		for(int i=0;i<=length-1;i++)
		{
			int t=i+1;
			System.out.println("第"+t+"个元素为"+sqlist[i]);
		}
	}
	//删除顺序表指定位置的元素
	public static int listDelete(int i) {
		if(i<1||i>length)
		{
			System.out.println("删除位置不合法");
			return -1;
		}
		for(int j=i;j<=length-1;j++)
		{
			sqlist[j-1]=sqlist[j];
		}
		length--;
		return 0;
	}
	public static void main(String[] args) {
		Sqlist sqlist = new Sqlist(5);
		for(int i=1;i<=4;i++)
		{
			sqlist.listInsert(i, i);
		}
		printList();
		System.out.println("第3个元素为"+getElem(3));
		listDelete(2);
		System.out.println("删除第二个元素后的顺序表的内容为：");
		printList();
	}
}

第二种

package SqueneList;

public class Linklist {
	
	static Node head = null;
	//使用内部类来作为普通结点，这样就只有头结点可以操作其他节点
	class Node{
		Node next=null;
		int data;
		public Node(int data) {
			this.data = data;
		}
	}
	//获取单链表的长度
	public static int getLength() {
		int length = 0;
		Node temp = head;
		while(temp.next!=null) {
			length++;
			temp = temp.next;
		}
		return length;
	}
	//单链表的增加
	public void addNode(int d) {
		Node newnode = new Node(d);
		if(head == null) {
			head = newnode;
			return;
		}
		Node temp = head;  //临时结点
		while(temp.next != null) {
			temp = temp.next;
		}
		temp.next = newnode;
		}
	//删除指定位置的结点
	public static boolean deleteNode(int i) {
		if(i<1||i>getLength()) {
			System.out.println("删除位置不合法");
			return false;
		}
		if(i==1) {
			head = head.next;  //若删除第一个结点则直接删去头结点即可
			return true;
		}
		int index=1;
		Node pre = head;  //定义两个临时结点分别为前驱结点与后继结点
		Node cur = pre.next;
		while(cur!=null) {
			if(index == i-1) {
				pre.next = cur.next;
				return true;
			}
			pre = cur;
			cur = cur.next;
			index++;
		}
		return false;
	}
	//打印单链表
	public static void printLinkList() {
		Node temp = head;
		while(temp != null) {
			System.out.println(temp.data);
			temp = temp.next;
		}
	}
	//链表的经典应用1:反转
	public static Node reverseList(Node head) {
		if(head == null) {
			return head;
		}
		Node pre = head;
		Node cur = head.next;
		Node tmp;
		while(cur!=null) {
			tmp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = tmp;
		}
		head.next = null;
		return pre;
	}
	//链表的经典应用2:查找单链表的中间节点
	public static int searchMid() {  //这里对单链表中间位置查找使用的是快慢指针法
		Node f = head;               //即：快的指针一次走两个慢的指针一次走一个，快的指针到达
		Node s = head;               //表尾时慢指针刚好走到表中
		while(f!=null&&f.next!=null&&f.next.next!=null) {
			f = f.next.next;
			s = s.next;
		}
		return s.data;
	}
	//链表的经典应用2:删除单链表中倒数第k个节点
	public static Node searchElem(int k) {
		if(k>getLength()||k<1) {
			System.out.println("删除位置不合法");
			return null;
		}
		Node pf = head;
		Node ps = head;
		for(int i=0;i<k;i++) {
			pf = pf.next;
		}
		while(pf!=null) {
			pf = pf.next;
			ps = ps.next;
		}
		return ps;
	}
	//对链表进行排序
	public static Node sortList() {
		Node nextNode = null;
		int temp = 0;
		Node curNode = head;
		while(curNode.next!=null) {
			nextNode = curNode.next;
			while(nextNode!=null) {
				if(curNode.data>nextNode.data) {
					temp = curNode.data;
					curNode.data = nextNode.data;
					nextNode.data = temp;
				}
				nextNode = nextNode.next;
			}
			curNode = curNode.next;
		}
		return head;
	}
	//删除链表中重复的节点就用简单的遍历方法 如果数据相同则p.next = p.next.next跳过就可以了
	//用递归的方法输出链表
	public static void diGuiPrint(Node head) {
		if(head!=null) {
			diGuiPrint(head.next);
			System.out.println("采用递归的方式输出链表："+head.data);
		}
	}
	public static void main(String[] args) {
		Linklist linklist = new Linklist();
		linklist.addNode(1);
		linklist.addNode(2);
		linklist.addNode(3);
		linklist.addNode(4);
		printLinkList();
		deleteNode(2);
		System.out.println("删除第二个结点后的单链表为：");
		printLinkList();
		head = reverseList(head);
		System.out.println("单链表反转后变为：");
		printLinkList();
		System.out.println("中间节点的数据为"+searchMid());
		System.out.println("倒数第2个节点的数据为"+searchElem(2).data);
		sortList();
		System.out.println("排序后的链表数据为:");
		printLinkList();
		diGuiPrint(head);
	}
}