浅谈数据结构之线性表（一）

秒速五厘米 2022-10-01 05:55 175阅读 0赞

### 数据结构之线性表（一） ###

*  基本概念
 *  数组和链表
 *   *   *   *   *  数组的优点
                 *  数组的缺点
                 *  链表的优点
                 *  链表的缺点
                 *  操作效率
 *  单链表、双链表、循环链表
 *   *   *   *   *  单链表
                 *  双链表
                 *  循环链表
 *  基本操作
 *  基本操作实战

# 基本概念 #

线性表是一种逻辑结构，相同数据类型的n个数据元素的有限序列，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。  
线性表具有以下特点：

*  元素个数有限
 *  逻辑上元素有先后次序
 *  数据类型相同
 *  仅讨论元素间的逻辑关系  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]

# 数组和链表 #

##### 数组的优点 #####

*  随机访问性强
 *  查找速度快

##### 数组的缺点 #####

*  插入和删除效率低
 *  可能浪费内存
 *  内存要求高，必须有连续的内存空间
 *  数组大小固定，不能动态扩展

##### 链表的优点 #####

*  插入删除速度快
 *  内存利用率高，不会浪费内存
 *  大小内有固定，拓展很灵活

##### 链表的缺点 #####

*  不能随机查找，必须从第一个开始遍历，查找效率低

##### 操作效率 #####

# 单链表、双链表、循环链表 #

##### 单链表 #####

![在这里插入图片描述][20190611164153274.png]

##### 双链表 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]

##### 循环链表 #####

1.  循环单链表  
    与单链表的区别在于，表中最后一个节点的指针不为null，而改为指向头结点（第一个节点），从而整个链表形成一个环。判断循环单链表是否为空，判断是否等于头指针。只有一个尾指针的循环单链表，可以很方便的操作表头和表尾，因为尾指针的后继就是头指针O(1) 。
2.  循环双链表  
    与双链表的区别在于，头结点的prior指针指向尾节点，尾节点的next指针指向头结点。

# 基本操作 #

1.  头节点插入  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 2]
2.  尾节点插入  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 3]
3.  插入  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 4]
4.  删除  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 5]

# 基本操作实战 #

数据结构存储类 ListNode.java
    public class ListNode { 
    
    	public int value;
    	
    	public ListNode next;
    	
    	public ListNode(int value) { 
    		this.value = value;
    	}
    }

操作方法类 MyList.java
    public class MyList { 
    	
    	
    	/** * 头节点插入 * @param head * @param newNode */
    	public static void headInsert(ListNode head, ListNode newNode) { 
    		newNode.next = head;
    	}
    	
    	/** * 尾节点插入 * @param tail * @param newNode */
        public static void tailInsert(ListNode tail, ListNode newNode) { 
    		tail.next = newNode;
    	}
    	
        /** * 遍历 * @param head */
        public static void traverse(ListNode head) { 
        	while (head != null) { 
    			System.out.print(head.value + " ");	
    			head = head.next;
    		}
        }
        
        /** * 查找 * @param head * @param value * @return */
        public static int find(ListNode head, int value) { 
        	int index = -1;
        	int count = 0;
        	while (head != null) { 
    			if (value == head.value) { 
    				index = count;
    				break;
    			}	
    			head = head.next;
    			count ++;
    		}
        	return index;
        }
        
    	/** * 插入 * @param p * @param s */
    	public static void insert(ListNode p, ListNode s) { 
    		ListNode next = p.next;
    		p.next = s;
    		s.next = next;
    	}
    	
    	/** * 删除 * @param head * @param q */
    	public static void delete(ListNode head, ListNode q) { 
    		if (q.next != null) { 
    			ListNode next = q.next;
    			q.value = next.value;
    			q.next = next.next;
    			next = null;
    		} else { 
    			while (head != null) { 
    				if (head.next == q) { 
    					head.next = null;
    					q = null;
    					break;
    				}
    				head = head.next;
    			}
    		}
    	}
    	
        public static void main(String[] args) { 
    		ListNode node1 = new ListNode(1);
    		ListNode node2 = new ListNode(2);
    		ListNode node3 = new ListNode(3);
    		ListNode node4 = new ListNode(4);
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		//头节点插入
    		ListNode node0 = new ListNode(0);
    		headInsert(node1, node0);
    		System.out.print("头节点插入 :");
    		traverse(node0);
    		System.out.println();
    		//尾节点插入
    		ListNode node5 = new ListNode(5);
    		tailInsert(node4, node5);
    		System.out.print("尾节点插入 :");
    		traverse(node0);
    		System.out.println();
    		//遍历
    		System.out.print("遍历 :");
    		traverse(node0);
    		System.out.println();
    		//查找
    		int index = find(node0, 4);
    		System.out.print("查找结果位置：" + index);
    		//插入
    		ListNode node6 = new ListNode(6);
    		insert(node2, node6);
    		System.out.println();
    		//遍历
    		System.out.print("插入之后遍历 :");
    		traverse(node0);
    		//删除
    		delete(node0, node6);
    		System.out.println();
    		System.out.print("删除之后遍历 :");
    		traverse(node0);
    		//删除
    		delete(node0, node3);
    		System.out.println();
    		System.out.print("删除之后遍历 :");
    		traverse(node0);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]: /images/20220119/32cebca71dea48ad9e539951913a9ba1.png
[20190611164153274.png]: /images/20220119/e8ad9fdf252c41bb96d154715f0b8b44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]: /images/20220119/b4772b50090f4f16b7bbb9133ed23a78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 2]: /images/20220119/1682711428da4b9691d575f035ad4157.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 3]: /images/20220119/afe5ea480fb94750b285c6aa3e3c02b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 4]: /images/20220119/f90c4d3f1528445582de7cdaa4388f0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 5]: /images/20220119/57666fc171a14b97b3c0cd64e841e396.png