Java实现静态链表

青旅半醒 2023-07-08 06:00 57阅读 0赞

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

静态链表的原理就是用另一个对应的数组存储该节点指向的下一个节点的下标，暂且叫它游标。并且第一个节点不存储数据，游标指向备用链表的第一个空节点。链表尾节点用来指向首节点。备用链表的最后一个节点指向第一个存储数据的节点。  
![静态链表][2020022623465211.png]  
当向链表插入一个节点时，首先将数据存入第一个空节点，并将该节点的游标赋给首节点，因为该节点的游标存放的是下一个空节点的下标，即将首节点指向下一个空节点。然后将新插入数据的节点的下标改为插入位置上一个节点的游标，再将插入位置上一个节点的游标改为插入节点的下标。

当删除一个节点时，需要注意的时要将被删除节点释放，将该节点指向原来的第一个空节点，将首节点指向该节点。

看不懂的话可以去看视频，看视频容易理解点。

public class StaticList {
        
    
    	//输入字符串创建一个静态链表
    	int MAX = 20;
    	int[] next = new int[MAX];
    	char[] data = new char[MAX];
    	int l;
    	//链表初始化
    	public StaticList(String str) {
        
    		this.l = str.length();
    		char[]  c = str.toCharArray();
    		for(int i = 0;i < l;i++) {
        
    			data[i+1] = c[i]; 
    		}
    		
    		next[0] = l+1;
    		for(int i = 1;i<MAX-1;i++) {
        
    			next[i] = i+1;
    		}
    		next[l] = 0;
    		next[MAX-1] = 1;
    	}
    	//输出链表
    	public void printList() {
        
    
    		int k = next[MAX-1];
    		while(data[k]!='\u0000') {
        
    			System.out.print(data[k]);
    			k = next[k];
    		}
    		System.out.println();
    	}
    	//向指定的位置后面插入一个值
    	public boolean insertList(char c, int index) {
        
    		if(index < 0 || index > l) {
        
    			return false;
    		}
    		int k = next[0];
    		next[0] = next[k];
    		data[k] = c;
    		int m = MAX-1;
    		for(int i = 0;i<index;i++) {
        
    			m = next[m];
    		}
    		next[k] = next[m];
    		next[m] = k;
    		this.l++;
    		return true;
    	}
    	//删除指定位置的值
    	public boolean delete(int k) {
        
    		if(k < 1 || k > l) {
        
    			return false;
    		}
    		int m = MAX-1;
    		for(int i = 1;i<k;i++) {
        
    			m = next[m];
    		}
    		l--;
    		int n = next[m];
    		next[m] = next[n];
    		//将删掉的节点指向下一个备用节点，将头节点指向删掉的节点
    		next[n] = next[0];
    		next[0] = n;
    		return true;
    	}
    	//修改链表指定位置的值
    	public boolean change(char c, int index) {
        
    		if(index<1 || index > l) {
        
    			return false;
    		}
    		int m = MAX - 1;
    		for(int i=0;i<index;i++) {
        
    			m = next[m];
    		}
    		data[m] = c;
    		return true;
    	}
    	//查询链表指定位置的值
    	public char get(int index) {
        
    		int m = MAX - 1;
    		for(int i=0;i<index;i++) {
        
    			m = next[m];
    		}
    		return data[m];
    	}
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    
    		StaticList sl = new StaticList("xghsocool!");
    		System.out.println(sl.delete(11));
    		
    		System.out.println(sl.l);
    		sl.printList();
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982
[2020022623465211.png]: https://img-blog.csdnimg.cn/2020022623465211.png