Java 实现链表结点插入

来自:网络
时间:2021-03-07
阅读:

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

为什么需要链表?

我们知道,数组也可以存储数据,那么为什么还需要链表呢?接下来,我们来看看数组 和链表的区别:

1、数组就像身上编了号站成一排的人,要找第10个人很容易,根据人身上的编号很快就能找到。但插入、删除慢,要往某个位置插入或删除一个人时,后面的人身上的编号都要变。当然,加入或删除的人始终末尾的也快。

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

链表示意图

Java 实现链表结点插入

链表的建立

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;
  }

头插法示意图:

Java 实现链表结点插入

尾插法:从尾插入

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

尾插法示意图:

Java 实现链表结点插入

从任意结点插入

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;
  }

示意图:

Java 实现链表结点插入

完整代码:

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());
			}
		}

输出结果:

Java 实现链表结点插入

补充:java中创建链表,实现链表的尾部插入

我就废话不多说了,大家还是直接看代码吧~

package test;
//目标:创建链表,实现链表结点的尾部插入
class Node_5{
  private String data;
  public Node_5 nextNode;
  public void setData(String indata){
    this.data=indata;
  }
  public String getData(){
    return this.data;
  }
  public void setNextNode(Node_5 newNode){
    this.nextNode=newNode;
  }
  public Node_5 getNextNode(){
    return this.nextNode;
  }
  public void addData(String indata){
    setData(indata);
    Node_5 node_5=new Node_5();
    Node_5 head=node_5;
    if(node_5.getData()==null){
      node_5.setData(indata);
      System.out.println(node_5.getData());
    }
    else{
      node_5.setNextNode(node_5);  
      node_5.setData(indata);
      System.out.println(node_5.getData());
    }    
  }   
}

public class T_5 {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Node_5 node_5=new Node_5();
    for(int i=1;i<=3;i++){
      node_5.addData("第"+i+"结点");
    }
  }
}

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。如有错误或未考虑完全的地方,望不吝赐教。

返回顶部
顶部