Java 链表结点插入

全栈程序员站长

发布于 2022-08-13 09:55:38

4990

发布于 2022-08-13 09:55:38

大家好，又见面了，我是你们的朋友全栈君。

PS:链表是一种数据结构，而数据结构就是一种存放数据的方式。

为什么需要链表？ 我们知道，数组也可以存储数据，那么为什么还需要链表呢？接下来，我们来看看数组和链表的区别： 1、数组就像身上编了号站成一排的人，要找第10个人很容易，根据人身上的编号很快就能找到。但插入、删除慢，要往某个位置插入或删除一个人时，后面的人身上的编号都要变。当然，加入或删除的人始终末尾的也快。

2、链表就像手牵着手站成一圈的人，要找第10个人不容易，必须从第一个人一个个数过去。但插入、删除快。插入时只要解开两个人的手，并重新牵上新加进来的人的手就可以。删除一样的道理。

链表示意图

链表的建立

class TestLink{//创建一个外部类
	
	private Entry head;//指向头结点的引用
	public TestLink(){
		head = new Entry();//用结点类 new 一个头结点
	}
	
	class Entry{//Entry  创建一个结点内部类
		int data;//定义数据块
		Entry next;//定义地址块
		
		public Entry(){//构造方法1
			data = -1;//对结点数据块初始化
			next = null;//对地址初始化
		}
		public Entry(int val){//构造方法2
			data = val;//对数据块赋值
			next = null;
		}
	}
}
public class TestDemo2 {

			public static void main(String[] args) {
				TestLink testlink = new TestLink();
				//创建一个 链表外部类 对象
    }
}

头插法：从头插入

public void insertHead(int val){
				//有这么一个结点  
				Entry cur = new Entry(val);
				cur.next = head.next;
				head.next = cur;
			}

头插法示意图：

尾插法：从尾插入

public void insertTail(int val){
				//找到尾巴
				Entry cur = head;
				while(cur.next != null){//遍历结点
					cur = cur.next;
				}
				Entry entry = new Entry(val);//得到的结点
				cur.next = entry;
			}

尾插法示意图：

从任意结点插入

public boolean insertPos(int val,int pos){
				//1、判断pos的合法性
				if(pos < 0 || pos >= getLength()+1){
					return false;
				}
				Entry cur = head;
				for(int i = 0;i <= pos-1;i++){
					cur = cur.next;
				}
				//cur    pos的前一个
				Entry entry = new Entry(val);
				entry.next = cur.next;
				cur.next = entry;
				return true;
			}

示意图：

完整代码：

package LianBiao;
class TestLink1{
	
	
	private Entry head;//指向头结点的引用
	
	public TestLink1(){
		head = new Entry();
	}
	
	class Entry{//Entry  Node 
		int data;
		Entry next;
		
		public Entry(){
			data = -1;
			next = null;
		}
		
		public Entry(int val){
			data = val;
			next = null;
		}
		
	}
	
	
	public void insertHead(int val){
		//有这么一个结点  
		Entry cur = new Entry(val);
		cur.next = head.next;
		head.next = cur;
		/*head.next = cur;
		cur.next = head.next;*/
	}
	
	public void insertTail(int val){
		//找到尾巴
		Entry cur = head;
		while(cur.next != null){
			cur = cur.next;
		}
		Entry entry = new Entry(val);//得到的结点
		cur.next = entry;
	}
	//得到单链表的长度：
	public int getLength(){
		int len = 0;
		Entry cur = head.next;
		while(cur != null){
			len++;
			cur = cur.next;
		}
		return len;
	}
	//将数据插入到指定位置
	public boolean insertPos(int val,int pos){
		//1、判断pos的合法性
		if(pos < 0 || pos >= getLength()+1){
			return false;
		}
		Entry cur = head;
		for(int i = 0;i <= pos-1;i++){
			cur = cur.next;
		}
		//cur    pos的前一个
		Entry entry = new Entry(val);
		entry.next = cur.next;
		cur.next = entry;
		return true;
	}
	//
	
	//show()
	public void show(){
		/*Entry cur = head;
		while(cur.next != null){
			System.out.println("data:"+cur.next.data);
			cur = cur.next;
		}*/
		Entry cur = head.next;
		while(cur != null){
			System.out.println("data:"+cur.data);
			cur = cur.next;
		}
	}
	
}

public class LianBiao1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

				TestLink1 testlink = new TestLink1();
				
				testlink.insertTail(1330);
				testlink.insertTail(110);
				//1330 110 
				testlink.insertPos(10,0);
				//10 1330 110
				
				if(testlink.insertPos(32,10000)){
					System.out.println("插入成功");
				}else{
					System.out.println("插入失败");
				}
				
				//10 32 1330 110
				
				testlink.show();
				System.out.println(testlink.getLength());
			}

		}

输出结果：