【数据结构真不难】线性表——五一专属|向所有热爱分享的“技术劳动者”致敬

 //第i的地址 = 第一个地址 + 第几个 *   存储单位Loc(ai)   =  Loc(a0) +    i   *   c

public class SqList {
    private Object[] listElem;		//线性表的存储空间
    private int curLen;				//线性表的当前长度
}

/**
 * @Param i 第i个位置
 * @Param x 需要插入的数据
 */
public void insert(){
    //0.1满校验：存放实际长度 和 数组长度一样
    if(curLen == listEle.length){
        throw new Exception("已满");
    }
    //0.2非法校验 在已有的数据中插入[0,curLen]必须连续 中间不能空元素
    if(i < 0 || i > curLen){
        throw new Exception("位置非法");
    }
    //1 将i及其之后移
    for(int j = curLen; j > i; j--){
        listEle[j] = listEle[j - 1];
    }
    //2 插入i处
    listEle[i] = x;
    //3 记录长度
    curLen++;
}

public void remove(int i){
    //0.1校验非法数据
    if(i < 0 || i > curLen - 1){
        throw new Exception("位置非法");
    }
    //1 将i之后向前移动
    for(int j = i; j < curLen - 1; j++){
        listEle[j] = listEle[j+1];
    }
    //2 长度--
    curLen--;
}

public int indexOf(Object x){
    for(int i = 0; j < curLen; i++){
        if(listEle[i].equals(x)){
            return i;
        }
    }
    return -1;
}

public int indexOf(Object x){
    int j = 0;    //用于记录索引信息
    while(j < curLen && !listEle[j].equals(x)){
        j++;
    }
    //j记录索引小于数量
    if(j < curLen){
        return j;
    }else{
        return -1;
    }   
}

public class Node{
    public Object data;				//数据域
    public Node next;				//指针域
}

public int length(){
    Node p = head.next;        //获得第一个节点
    int length = 0;            //定义一个变量记录长度
    while(p != null){
         length++;            //计数
         p = p.next;          //p指向下一个节点
    }
    return length;
}

public Object get(int i){
    Node p = head.next;                        //获得头节点
    int j = 0;
    while(p != null && j < i){                //已经处理的节点数
        p = p.next;                            //链表没有下一个 && 处理有效部分
        j++;
    }
    if(i < 0 || p == null){
        throw new Exception("元素不存在");
    }
    return p.data;    //返回数据
}

//查询给定值的索引号 如果没有返回-1
public int indexOf(Object x){
    Node p = head.next;        //获得头节点
    int j = 0;                //不匹配元素的个数
    while(p != null && !p.data.equals(x)){    //循环依次找[不匹配]元素
        p = p.next;
        j++;
    }
    //返回匹配索引 如果没有返回-1
    if(p != null){
        return j;
    }else{    
        return -1;
    }

}

public void insert(int i,Object x){
    Node p = ......;            //获得i前驱
    Node s = new Node(x);       //创建新节点s
    s.next = p.next;            //必须先执行
    p.next = s;                //然后再执行
}

public void remove(int i){
    //获得i的前驱节点p
    p.next = p.next.next;
}

// i最小值0，表示获得头结点head
// 算法内部，使用-1表示头结点head，结点移动从头结点head开始。
public void previous(int i){
    Node p = head;
    int j = -1;
    while(p != null && j < i - 1){
        p = p.next;
        j++;
    }
    if(p != null || i < 0){
        throw new RuntimeException("i不合法");
    }
}

// p结点是尾结点
p.next = head;

/* 变量
	a尾: taila
	a头：taila.next
	b尾：tailb
	b头：tailb.next
*/
// 先将b尾指向a的头，需要定义p记录b尾原来的值
// 再将a的尾指向b的头
Node p = tailb.next;			//记录b尾的指向，也就是b头
tailb.next = taila.next;		//b尾指向a头
taila.next = p.next;			//a尾执行b头

/* 变量
	结点a：p.prior
*/
p.prior.next = s;		//结点a指向结点s
s.prior = p.prior;		// 结点s指向结点a

p.prior = s;			//结点p指向结点s
s.next = p;				//结点s执行结点p
//注意：必须先处理结点a，否则无法获得结点a

// a.next = b
p.prior.next = p.next;
// b.prior = a
p.next.prior = p.prior