单链表的讲解：单链表的原理，添加、删除元素

ゞ浴缸里的玫瑰 2022-04-22 14:40 180阅读 0赞

单链表及其节点

链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，  
一个域用于数据元素的存储，另一个域是指向其他单元的指针。  
这里具有一个数据域和多个指针域的存储单元通常称为 结点（node）

一种最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，  
指针域用于指向下一个具有相同结构的结点。  
因为只有一个指针结点，称为单链表   
 ![70][]  
      
链表的第一个结点和最后一个结点，分别称为链表的 首结点和 尾结点。  
尾结点的特征是其 next 引用为空（null）。  
链表中每个结点的 next 引用都相当于一个指针，指向另一个结点，  
借助这些 next 引用，我们可以从链表的首结点移动到尾结点。  
在单链表中通常使用 head 引用来指向链表的首结点，由 head 引用可以完成对整个链表中所有节点的访问。

![70 1][]  
    在单链表结构中还需要注意的一点是，由于每个结点的数据域都是一个 Object 类的对象，  
    因此，每个数据元素并非真正如图中那样，而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。  
与数组类似，单链表中的结点也具有一个线性次序，即如果结点 P 的 next 引用指向结点 S，则 P 就是 S 的直接前驱，S 是 P 的直接后续。  
单链表的一个重要特性就是只能通过前驱结点找到后续结点，而无法从后续结点找到前驱结点。

#    单链表的查询、添加、删除操作分析 #

##    **查询操作** ##

在单链表中进行查找操作，只能从链表的首结点开始，通过每个结点的 next 引用来一次访问链表中的每个结点以完成相应的查找操作。  
      
例如需要在单链表中查找是否包含某个数据元素 e，则方法是使用一个循环变量 p，起始时从单链表的头结点开始，  
每次循环判断 p所指结点的数据域是否和 e 相同，如果相同则可以返回 true，否则让p指向下一个节点，继续循环直到链表中所有  
结点均被访问，此时 p 为 null  
     ![70 2][]

关键操作：  
        1.起始条件：p = head;  
        2.结束条件：  
            找到：e.equals(p.getData())==true  
            未找到  p == null  
        3.p指向下一个结点: p  = p.getNext();  
          
        缺点：逐个比较，频繁移动指针，导致效率低下  
          
        注意：如果要查询第i个元素的值，无法直接定位，也只能从首结点开始逐个移动到第i个结点，效率同样低下。

## 添加操作 ##

在单链表中数据元素的插入，是通过在链表中插入数据元素所属的结点来完成的。  
    对于链表的不同位置，插入的过程会有细微的差别。  
    中间、末尾的添加过程其实是一样的，关键是在首部添加，会有不同，会改变整个单链表的起始结点。  
      
     ![70 3][]

以添加中间结点为例  
        1.指明新结点的后继  s.setNext(p.getNext());   或者 s.next = p.next  
        2.指明新结点的前驱（其实是指明前驱结点的后继是新结点） p.setNext(s)    或者 p.next = s;  
          
    添加节点不需要移动元素，只需要修改元素的指针即可，效率高。  
    但是如果需要先查询到添加位置再添加新元素，因为有逐个查询的过程，效率不高。

## 删除操作 ##

类似添加操作  
         ![70 4][]  
           
      
    在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的最前面添加一个哑元结点，也称为头结点。  
    在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点，  
    可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。  
    一个带头结点的单链表实现线性表的结构图如图 所示。  
     ![70 5][]

单链表的代码实现：

/**
     * 单链表
     * @author Administrator
     *
     */
    public class SingleLinkedList implements List{
    	
    	public Node head = new Node();//只有一个头结点
    	
    	public int size;//默认长度是0，头结点不算
    	
    	public SingleLinkedList(){
    		
    	}
     
    	@Override
    	public int size() {
    		
    		return size;
    	}
    	/**
    	 * 和数组可是不一样了！！！
    	 */
    	@Override
    	public Object get(int i) {
    		return null;
    	}
     
    	@Override
    	public boolean isEmpty() {		
    		return size == 0;
    	}
     
    	@Override
    	public boolean contains(Object e) {		
    		return this.indexOf(e)>=0;
    	}
     
    	@Override
    	public int indexOf(Object e) {
    		Node p = head.getNext();
    		for(int i = 0 ;i<size;i++){
    			//取出当前结点的值
    			Object data = p.getData();
    			//判断是否相同
    			if(e.equals(data)){
    				return i;
    			}
    			//移动指针
    			p = p.getNext();
    		}
    		
    		return -1;
    	}
     
    	@Override  
    	public void add(int i, Object e) {
    		//判断i的范围，提高健壮性
    		if(i<0 || i>size){
    			throw new IndexOutOfBoundsException("索引越界异常："+i);
    		}
    		//定位到前一个结点
    		Node p = head;
    		for(int j = 0 ;j<i;j++){
    			p = p.getNext();
    		}
    		
    		//创建一个新结点
    		Node s = new Node();
    		s.setData(e);
    		
    		//完成添加操作
    		s.setNext(p.getNext());//指明新结点的后继
    		p.setNext(s);//指明新结点的前驱（其实是指明前驱结点的后继是新结点）
    		
    		//size增1
    		size++;
    	}	
    	
     
    	@Override
    	public void add(Object e) {
    		int i = this.size;
    		this.add(i,e);
    		
    	}
     
    	@Override
    	public boolean addBefore(Object obj, Object e) {
    		return false;
    	}
     
    	@Override
    	public boolean addAfter(Object obj, Object e) {
    		return false;
    	}
     
    	@Override
    	public Object remove(int i) {
    		
    		return null;
    	}
     
    	@Override
    	public boolean remove(Object e) {
    		//先确定前驱结点和要删除结点
    		Node p = head;  
    		Node s = head.getNext();
    		boolean flag = false;//默认该结点不存在
    		while(s!= null ){
    			//判断是否找到
    			if(e.equals(s.getData())){
    				flag = true;
    				break;
    			}
    			//如果没有找到，移动指针到后一个结点
    			p = s;
    			s = s.getNext();			
    		}
    		//如果找到，就删除
    		if(flag){
    			p.setNext(s.getNext());
    			s.setNext(null);
    			s =null;
    		}
    		return flag;
    		
    	}
     
    	@Override
    	public Object replace(int i, Object e) {
    		return null;
    	}
     
    	@Override
    	public String toString() {
    		StringBuilder builder = new StringBuilder("[");
    		Node p = head.getNext();
    		while(p!=null){			
    			//取出结点值
    			Object data = p.getData();
    			//加入StringBuffer
    			builder.append(data+",");
    			//后移一个结点
    			p = p.getNext();
    		}
    		//删除最后的一个逗号
    		if(builder.length()>1){
    			builder.deleteCharAt(builder.length()-1);
    		}
    		builder.append("]");
    		
    		return builder.toString();
    	}
    	
    	
    }
     
     
    	测试类
    public class Test {
    	
    	public static void main(String[] args) {
    		//创建线性顺序表
    		List list = new SingleLinkedList();
    		//向末尾添加元素
    		list.add("11111");
    		list.add("aaaaa");
    		list.add("bbbbb");
    		list.add("33333");
    		list.add("22222");
    		
    		list.add(2, "AAAAA");
    		System.out.println(list.toString());
    		list.remove("AAAAA");
    		System.out.println(list.toString());
    		//进行各种操作验证添加
    //		System.out.println(list.size());
    //		System.out.println(list.isEmpty());
    //		System.out.println(list.contains("AAAAA"));
    //		System.out.println(list.indexOf("22222"));
    //		
    //		System.out.println(list.toString());
    		
    	}
     
    }

作业  
1.提取获取第i结点前一个结点方法：getPreviousNode(int i)  
   提取data是e结点前一个结点方法：getPreviousNode(Object e)  
   并进行重用  
2.完成SingleLinkedList类没有实现的方法

[70]: /images/20220414/cb9422ef56b2468283a5a7a112b07b74.png
[70 1]: /images/20220414/8fe283ea583c41cba9f0fd9adac5ba42.png
[70 2]: /images/20220414/c0c12a3b69f94489a274bb8afb57923e.png
[70 3]: /images/20220414/afde14347d904312b543f79238483782.png
[70 4]: /images/20220414/718b5869aab14bfb9edcc0f785ef42e7.png
[70 5]: /images/20220414/648e730766d84034b7d3ced7f9b1302a.png