Coolshell for Fun

目录

1. 1. 链表中优化改进的方法
   1. 1.1. 将成员信息分离为新的类，简化用户交互。
   2. 1.2. 单独创建链表头，省去考虑成员为空时再次创建链表头的情况，也提高访问成员的效率。

链表中优化改进的方法

将成员信息分离为新的类，简化用户交互。

public class node {
    int data;
    node next;
    public node(int item, node nextNode) {
        data = item;
        next = nextNode;
    }
} 

单独创建链表头，省去考虑成员为空时再次创建链表头的情况，也提高访问成员的效率。

1. 这里的 head 可以创建两种结构，一种是闭环式的，即末端成员的 next 指向 head 。还有一种是两头式的，即创建另外一个 head 放在末尾。我觉得闭环式的可以看作隐式的两头式，它把两个 head 重叠了，（ 优点是更加方便访问成员了，缺点我觉得是缺少明确结束的条件，觉得会出无限循环的 bug 。）两头式的给出了明确的结束条件，但在访问成员时得考虑是成员还是 head 。

   public class SList {
       node head;
       head = new node(0, null);
   
       public void addFirst(int item) {
           head.next = new node(item, head.next);
       }
   }

   ## 对链表长度进行缓存，将访问长度的时间从线性改为常数。
2. 在对成员增加删除操作中，要额外增加对长度的修改操作。
3. 我觉得链表很长时，常数的访问时间就可以弥补对长度修改带来的复杂性问题了。（缺少实操，仅作猜想）

   int size = 0;
   
   /** For example: add size by 1 in addFirst method */
   public void addFirst(int item) {
       head.next = new node(item, head.next);
       size += 1;
   }

   ## 用双向链表将链表访问末端成员时间缩短。
4. 因为是双向链表，所以在修改链表成员时要注意两个方向都进行修改。虽然这里也是缩短了访问时间，但也增加了代码复杂度。
5. 闭环式的双向链表感觉在这里更好用，只要维护一个 head , 思考理解起来简单.

   /** add prev property to node */
   public node addLast(int item) {
       head.prev = new node(item, head.prev, head);
       head.prev.prev.next = head.prev;
   }
   
   public node removeLast(int item) {
       head.prev = head.prev.prev;
       head.prev.next = head;
   }

   ## 使用泛型，提高代码通用性
6. 仅作简单例子的记录，刚学，拿捏不准。

   public  class DLList<Type> {
       Type data;
       node prev;
       node next;
   
       public node(Type item, prevNode, nextNode) {
           data = item;
           prev = prevNode;
           next = nextNode;
       }
   
       public Type removeLast() {
           head.prev = head.prev.prev;
           head.prev.next = head;
       }
   }

   # 几个技巧性的链表的方法
7. 单向链表反转成员顺序 ： reverse()

   public void reverse() {
       node back; 
       node front;
       back = null;
       front = head.next;
   
       while (front != null) {
           node p = front.next;
           front.next = back; 
           back = front;
           front = p;
       }
   
       head = back;
   }

   # 利用数组存储数据 因为数组从一开始就是固定的，无论是添加首成员还是尾成员都有一定限度，这里面有几个问题要注意。
   
8. 添加成员的方向性问题。我觉得整体可以遵循从右往左的顺序，以某一个格子为基准，往左依次添加首成员, 往右依次添加尾成员。当左边满了以后，下一个首成员开始从数组最右边开始往左数，第一个空的就做为首成员。
   如图
   
9. 从数组开头跳转到数组末尾的问题。因为要是添加首成员时，我们可以简单的将当前首成员位置减去一，就是下一个首成员的位置。可是当当前成员在数组开头时，我们就不能减一，而是要跳到数组末尾。我的想法是按照链表的结构来想象数组，把数组想象为一个闭环。这样首尾就相连了, 虽然不能减一到达末尾，但我可以增加数组长度来试着到达末尾。这样以来又产生一个问题，即添加首成员时要分类讨论当前成员的位置。为了统一，我把所有的减都当作加来看待。这让我想起来学c语言时，
10. 伸缩数组长度问题。当数组成员高到或低到一定百分比时就需要扩增或缩减数组。这个百分比，我不太懂。这里先只说如何扩增。扩增前后必须保证数组成员方向性一致，才能保证对数组成员的操作一致! 我的想法是从数组尾端与首端成员相连处分开，在这中间插入数组。
    如下图所示
    
    下面是扩增之后的效果
    

    public class ALList() {
    
        private
    }