网站维护费计入什么科目,汕头seo网络推广服务,山东鲁桥建设有限公司网站,整合营销的特点基本概念
链表是一种物理存储结构上非连续、非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中指针链接次序实现的。和数组相比较#xff0c;链表不需要指定大小#xff0c;也不需要连续的地址。 单链表的基本设计思维是#xff0c;利用结构体的设置#xff0c…基本概念
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中指针链接次序实现的。和数组相比较链表不需要指定大小也不需要连续的地址。 单链表的基本设计思维是利用结构体的设置额外开辟一个空间去做指针指向下一个结点。 其中DATA是需要存储的数据元素可以为任何数据格式可以是数组可以是int还可以是结构体。 NEXT作为一个空指针其代表了一个可以指向的区域通常是用来指向下一个结点链表尾部NEXT指向NULL空因为尾部没有任何可以指向的空间了。
创建结点
private static class NodeE {private E item; private NodeE next;Node(E element,NodeE next){item element;this.next next;}
}创建接口java
public interface BaseTabT {/*** 空置链表*/public void clear();/*** 判断链表是否为空* return true 为空*/public boolean isEmpty();//获取链表中的元素个数public int length();//获取并返回线性表中的第i个元素public T get(int i);//添加一个元素public void insert(T t);//向第i个元素之前插入一个元素public void insert(int i,T t);//删除并返回第i个元素public T remove(int i);//返回指定元素的序号若不存在返回-1public int indexOf(T t);
}实现全部功能
public class SingleLinkedListE implements BaseTabE{private NodeE mHeader; //链表头部结点,头部结点不存储数据只存储nextprivate int size 0; //记录链表长度public SingleLinkedList(){}Overridepublic void clear() {mHeader.next null;size 0;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic int length() {return size;}Overridepublic E get(int index) {NodeE node mHeader;//从Header开始循环for(int i 0;i index;i){node node.next;}return node.item;}Overridepublic void insert(E data) {if(mHeader null){mHeader new NodeE(data,null);size;return;}NodeE lastNode mHeader;while (lastNode.next ! null){ //通过循环找到链表的尾部lastNode lastNode.next;}lastNode.next new Node(data,null);size;}Overridepublic void insert(int index, E data) {//创建新的结点用来存放数据if(mHeader null){mHeader new NodeE(data,null);size;return;}NodeE newNode new NodeE(data,null);NodeE preNode mHeader;for(int i 0;i index -1;i){ //循环找到index位置的前一个结点preNode mHeader.next;}newNode.next preNode.next;preNode.next newNode;size;}/*** 打印出链表所有数据*/public void printAll(){NodeE node mHeader;while (node.next ! null){System.out.println(node.item);node node.next;}System.out.println(node.item);}Overridepublic E remove(int index) {//1.找到指定位置的前一个NodeNodeE preNode mHeader;for(int i 0; i index -1;i){preNode preNode.next;}//需要被删除的NodeNodeE removeNode preNode.next;preNode.next removeNode.next;size--;return removeNode.item;}Overridepublic int indexOf(E data) {Node node mHeader;for(int i 0;i size;i){if(node.item.equals(data)){return i;} else {node node.next;}}return -1;}private static class NodeE {private E item;private NodeE next;Node(E element,NodeE next){item element;this.next next;}}
}反转链表
链表反转是一道比较常见的面试题 eg链表中输入01234输出 43210 实现一个结点
public class NodeT {T data; //数据NodeT next; //指向下一个结点public Node(T value){data value;}
}从结点的结构上面来说我们需要修改的是next将next由指向下一个改成指向上一个。 链表全部反转那就需要从尾部或者头部开始从尾部开始的话使用递归的思想。 public static T NodeT reversalLink(NodeT head){//主要是通过head.next null 找出最后面的一个结点if(head null || head.next null) return head;//通过递归找到最后的一个作为Head//递归执行顺序是43210NodeT revHead reversalLink(head.next);//调整指针//eg:执行到3时需要做以下操作//1.4的next应该是3当head 3时 目前head.next 4 4.next head就将4的下一个结点指向3head.next.next head;//执行上上一步后3-4,4-3,现在需要将3-4断开head.next null;return revHead;}public static void main(String[] args) {NodeInteger head new Node(0);NodeInteger node1 new Node(1);NodeInteger node2 new Node(2);NodeInteger node3 new Node(3);NodeInteger node4 new Node(4);head.next node1;node1.next node2;node2.next node3;node3.next node4;//反转前NodeInteger node head;while (node ! null){System.out.print(node.data );node node.next;}System.out.println();System.out.println(-----反转后-------);NodeInteger revHead reversalLink(head);while (revHead ! null){System.out.print(revHead.data );revHead revHead.next;}}从链表头部开始 思路就如上面所画从header开始拆成两个链表 public static T NodeT reversalLink1(NodeT head){NodeT preNode null;NodeT curNode head;while (curNode ! null){NodeT nextNode curNode.next;curNode.next preNode;preNode curNode;curNode nextNode;}return preNode;}
