# 线性表
- 线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有**相同特性**的数据元素的**有限**序列
- **前驱元素**：若A元素在B元素的前面，则称A为B的前驱元素
- **后继元素**：若B元素在A元素的后面，则称B为A的后继元素

## 顺序表
### 定义
- 顺序表是在计算机内存中以**数组**的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
### 代码

```java
package list;

/**
 * @author LZH.create
 * Date 2012.3.16
 * 效率
 */
public class SequenceList {

private String [] eles  ;
	// 当前 线性表 元素的个数
	private int n ;
	
	
	
	// 构造方法    capacity  容量
	public  SequenceList(int  capacity) {
	eles = new String [capacity] ;
	n = 0 ;
	}
	
	
    public void clear() {
    	n = 0 ;
    	// 将整个数据置空
    	eles = new String [eles.length] ;
    } 
    
    
    // 判空 
    public boolean isEmpty() {
    	return n == 0 ;
    }
    
    public int length () {
    	return   n ;
    }

public String get(int index) {
    	
    	if (index < 0 || index >= n) {
    		System.err.println("当前元素不存在")   ;
    		return null ;
    	}
    	
    	return  eles[index];
    }
    
    
    // 在线性表第 i  个元素之前插入  v
    
    public void insert(int i , String v) {
    	
    	// 判断是否已表满
    	if( n == eles.length) {
    		System.err.println("当前表以满") ;
    		  return ;
    		}  
    	
    	
    	if(i >= eles.length) {
    		System.err.println("下标位置非法") ;
    	}
    	
    	// 判断 i  是否合法
    	if (i < 0 ||  i > n ) {
    		System.err.println("下标位置非法") ;
    		return ;
    	}
    	
    	//  把  v  放于 i(index ) 处
    	eles[i] = v ;
    	n++ ;
     }
    
    
    public void insert(String v) {
    	if( n == eles.length) {
    		System.err.println("当前表以满") ;
    		  return ;
    		}  
    	
    	eles[n++] = v ;
    }
    
    
    public String remove( int index) {
    	
    	if (index < 0 || index >= n) {
    		System.err.println("当前元素不存在")   ;
    		return null ;
    	}
    	
    	// 获取要删除的元素
    	String result = eles[index] ;
    	
    	for( int i = index  ; i < n- 1 ; i++) {
    		eles [i] = eles [i + 1] ; 
    	}  
    	
    	n -- ;
    	
    	return  result  ;
    }
    
    
    
    // 返回线性表 首次出现的元素的索引
    public int indexOf(String v) {
    	return 0 ;
    }
}

class Test1{
	public static void main(String [] args) {
		SequenceList list = new SequenceList(10) ;
		list.insert("热爱");
		list.insert("效率");
		list.insert("格局");
		list.insert("心态");
		
         System.out.println(list.get(1));
         System.out.println(list.remove(0));
         System.out.println(list.get(0));
         list.clear(); 
         System.out.println(list.length());
		
	}
}

```

## 链表
### 定义
- 链表是一种物理存储单元上**非连续、非顺序**的存储结构，其物理结构不能直观的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每个元素称为结点）组成结点可以在运行时动态生成。

### 代码

```java
package list;

public class LinkList {
	
	// 首结点
	private  Node head ;
	// 链表长度
	private int n ;
	
	
	public LinkList() {
		n = 0 ;
		head = new Node(null,null) ;
	}
	
	
	// 对象  结构体
	private  static class Node {

public String item ;
		public Node next ;
		
	
		//  右键 source  构造方法快捷键
		public Node(String item, Node next) {
			super();
			this.item = item;
			this.next = next;
		}
	
		
	}
	
	
	   public void clear() {
		   
		   head.item = null ;
		   head.next = null ;
		   n = 0 ;
	    	
	    } 
	    
	    
	    // 判空 
	    public boolean isEmpty() {
	    	return n== 0 ;
	    }
	    
	    public int length () {
	    	return   0 ;
	    }

public String get(int index) {
	    	
	         if(index < 0  || index >= n) {
	        	 System.err.println("下标不合法") ;
	        	 return null;
	         }
	    	
		    // 获取第一个结点
	    	Node item = head.next  ;
	    	for (int i = 0 ; i < index ; i++) {
	    		item = item.next ;
	    	}  
	    	return item.item ;
	    }

// 在线性表第 i  个元素之前插入  v
	    
	    public void insert(int index , String v) {
	    	if (index < 0 || index >= n) {
	    		System .err.println("位置不合法");
	    	    return ;
	    	} 
	    	
	    	Node pre = head ;
	    	for( int i = 0 ; i < index ; i++) {
	    		pre = pre.next ;
	    	} 
	    	
	    	Node next = pre.next ;
	    	
	    	Node newNode = new Node(v,next) ;
	    	pre.next = newNode ;
	    	
	    	n++ ;
	           
	     }
	    
	    
	    public  void  resize(int newSize) {
	    	
	    }
	    
	    
	    // 尾插法
	    public void insert(String v) {
	    	
	    	Node  node = head ;
	    	
	    	while(node.next != null) {
	    		node = node.next ;
	    	}
	    	
	    	
	    	Node newNode = new Node(v,null) ;
	    	node.next = newNode ;
	    	n ++ ;
	    	
	    }
	    
	    
	    public String remove( int index) {
	    	if(index < 0 || index >= n) {
	    		System.err.println("下标位置不合法") ;
	    		return null ;
	    	}  
	     
	    	Node pre = head  ;
	    	// 寻找  index  之前的元素
	    	for (int i = 0 ; i < index ; i++) {
	    		pre = pre.next ;
	    	}
	    	
	    	
	    	// 获取 当前结点的位置
            // current 为当前节点的位置    	    	
	    	Node  current = pre.next ;
	    	Node next = current.next ;
	    	
	    	pre.next = next ;
	    	n-- ;
	    	return current.item  ;
	    }
	    
	    
	    
	    // 返回线性表 首次出现的元素的索引
	    public int indexOf(String v) {
	    	return 0 ;
	    }
	
	public static void main(String[] args) {
		Node node1 = new Node("a",null) ;
		Node node2 = new Node("b",null) ;
		Node node3 = new Node("c",null) ;
		
		node1.next = node2;
		node2.next = node3;
		
	}

}

class Test3{
	public static void main(String [] args) {
		LinkList list = new LinkList() ;
		list.insert("数据结构");
		System.out.println(list.get(0));
		list.insert("计算机组成原理");
		System.out.println(list.get(1));
		list.insert(0,"计算机网络") ;     // 带序号插入
		System.out.println(list.get(0)+list.get(1));
		System.out.println(list.remove(1));
		System.out.println(list.get(1));
		System.out.println(list.length());
		list.clear(); 
		System.out.println(list.length());
		System.out.println(list.isEmpty());
	}
}

```
## 双向链表
### 定义
- 双向链表也叫双向表，是链表的一种，它由多个结点組成，毎个结点都由一个**数据域**和两个**指针域**组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的欻据域不存诸数据，指向前驱结点的指针域值为`null`，指向后继结点的指针域指向第一个真正存储数据的结点。

### 图解
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210317183926981.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1F1YW50dW1Zb3U=,size_16,color_FFFFFF,t_70)
### API  设计
####  节点 API
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210319211429805.png)

#### 双向链表 API
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210317192951268.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1F1YW50dW1Zb3U=,size_16,color_FFFFFF,t_70)

### 代码
整体代码
```java
package list;

/**
 * @author LZH.create
 *  @Date 2021.3.19
 *    劝君专注案前事
 */
public class TowWayLinkList {
	
	// 首结点
	private  Node first ;
	private  Node last ; 
	// 链表长度
	private int n ;

// 对象  结构体
	private  static class Node {

public String item ;
		public Node next ;
		public Node pre ;
		
	
		//  右键 source  构造方法快捷键
		public Node(String item,Node pre , Node next) {
			super();
			this.item = item;
			this.pre = pre;
			this.next = next;
		}
	
		
	}
	  public TowWayLinkList() {
		  last = null ;
		  first = new Node(null,null,null) ;
		  n = 0 ;
	  }
	
	   public void clear() {
		   last = null ;
		   first.item = null ;
		   first.next = null ;
		   first.pre = null ;
		   n = 0 ;
	    	
	    } 
	    
	    
	    // 判空 
	    public boolean isEmpty() {
	    	return n== 0 ;
	    }
	    
	    public int length () {
	    	return   0 ;
	    }

public String get(int index) {
	    	
	         if(index < 0  || index >= n) {
	        	 System.err.println("下标不合法") ;
	        	 return null;
	         }
	    	
		    // 获取第一个结点
	    	Node item = first.next  ;
	    	for (int i = 0 ; i < index ; i++) {
	    		item = item.next ;
	    	}  
	    	return item.item ;
	    }

// 在线性表第 i  个元素之前插入  v    尾插法
	    
	    public void insert( String v) {
	    	
	    	// 注意此链表有头节点
	    	if (last == null) {
	    		last = new Node (v,first,null) ;
	    		first.next = last ;
	    	} else {
	    		Node oldLast = last ;
	    		Node node = new Node (v,oldLast,null) ;
	    		oldLast.next = node ;
	    		last = node ;
	    	}
	    	
	          n++ ;
	     }
	    
	    
	    public  void  resize(int newSize) {
	    	
	    }
	    
	    
	    // 指定位置插入
	    public void insert(int index ,String v) {
	    	if(index < 0 || index >= n) {
	    		System.err.println("下标位置不合法") ;
	    		return  ;
	    	} 
	    	
	    	// 获取头节点
	    	
	    	Node pre = first ;
	    	for (int i = 0 ; i < index ; i++) {
	    		pre = pre.next ;
	    	}
	    	
	    	Node next = pre.next ;
	    	Node newNode = new Node(v,pre,next) ;
	    	
	    	pre.next = newNode ;
	    	next.pre = newNode ;
	    	
	    	n++ ;
	    }
	    
	    
	    public String remove( int index) {
	    	if(index < 0 || index >= n) {
	    		System.err.println("下标位置不合法") ;
	    		return null ;
	    	}  
	     
	    	Node pre = first  ;
	    	// 寻找  index  之前的元素
	    	for (int i = 0 ; i < index ; i++) {
	    		pre = pre.next ;
	    	}
	    	
	    	
	    	// 获取 当前结点的位置
            // current 为当前节点的位置    	    	
	    	Node  current = pre.next ;
	    	Node next = current.next ;
	    	
	    	pre.next = next ;
	    	next.pre = pre ;
	    	n-- ;
	    	return current.item  ;
	    }
	    
	    
	    
	    // 返回线性表 首次出现的元素的索引
	    public int indexOf(String v) {
	    	return 0 ;
	    }
	    
	    
	    // 获取第一个与最后一个元素
	    
	    public String getFirst() {
	    	if (isEmpty()) {
	    		return null ;
	    	}
	    	return first.next.item ;
	    } 
	    
	    
	    public String getLast() {
	    	
	     	if (isEmpty()) {
	    		return null ;
	    	}
	    	return last.item ;
	    }
	
	public static void main(String[] args) {
	
	}

}

class Test4{
	public static void main(String [] args) {
		TowWayLinkList list = new TowWayLinkList() ;
		list.insert("数据结构");
		System.out.println(list.get(0));
		list.insert("计算机组成原理");
		System.out.println(list.get(1));
		list.insert(0,"计算机网络") ;     // 带序号插入
		System.out.println(list.get(0)+list.get(1));
		System.out.println(list.remove(1));
		System.out.println(list.get(1));
		System.out.println(list.length());
		list.clear(); 
		System.out.println(list.length());
		System.out.println(list.isEmpty());
	}
}

```
#### 局部代码分析
==注意==： 思考与普通链表的区别（尾插法）

```java
  public void insert(String v) {
	    	
	    	Node  node = head ;
	    	
	    	while(node.next != null) {
	    		node = node.next ;
	    	}
	    
	    	Node newNode = new Node(v,null) ;
	    	node.next = newNode ;
	    	n ++ ;
	    	
	    }
```

使用  `while`  语句 判断尾节点

---

```java
	    public void insert( String v) {
	    	
	    	// 注意此链表有头节点
	    	if (last == null) {
	    		last = new Node (v,first,null) ;
	    		first.next = last ;
	    	} else {
	    		Node oldLast = last ;
	    		Node node = new Node (v,oldLast,null) ;
	    		oldLast.next = node ;
	    		last = node ;
	    	}
	    	
	          n++ ;
	     }
```

Java 版数据结构——线性表

总共已有 0 条评论

Java 版 数据结构——线性表

总共已有 0 条评论

Java 版数据结构——线性表