算法数据结构（1）-单链表及LRU缓存实现

先看看效果

LruCache.gif

具体代码实现

• 实现单链表

public class LinkedList {

    Node first;
    int size;

    /**
     * 增加一个节点到链表头部
     */
    public void addFirst(String data) {
        Node node = new Node(data);
        if (first == null) {
            first = node;
        } else {
            node.next = first;
            first = node;
        }
        size++;
    }
    /**
     * 增加一个节点到链表尾部
     */
    public void addLast(String data) {
        if (first == null) {
            addFirst(data);
            size++;
            return;
        }
        Node node = new Node(data);
        Node temp = first;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        size++;
    }

    /**
     * 删除尾部结点
     * @return
     */
    public boolean removeLast() {
        if (size == 0) {
            return false;
        }

        Node temp = first;
        Node previous = first;
        while (temp.next != null) {
            previous = temp;
            temp = temp.next;
        }
        previous.next = null;
        size--;
        return true;
    }
    /**
     * 删除指定结点
     * @return
     */
    public boolean removeNode(String data) {
        if (size == 0) {
            return false;
        }

        Node temp = first;
        Node previous = first;
        while (!temp.data.equals(data)) {
            if (temp.next == null) {
                return false;
            } else {
                previous = temp;
                temp = temp.next;
            }
        }
        if (temp == first) {
            first = temp.next;
            size--;
        } else {
            previous.next = temp.next;
            size--;
        }

        return true;

    }

    /**
     * 查找指定结点
     * @param data
     * @return
     */
    public String getNode(String data){
        if (size == 0) {
            return null;
        }
        Node temp = first;
        while (!temp.data.equals(data)){
            if(temp.next == null){
                return null;
            }else {
                temp = temp.next;
            }
        }
        return temp.data;
    }

    public String getLinkedList() {
        StringBuilder builder = new StringBuilder();
        if (first.next == null) {
            builder.append(first.data);
        } else {
            Node temp = first;
            while (temp.next != null) {
                builder.append(temp.data + "->");
                temp = temp.next;
            }

            builder.append(temp.data + "->");
        }

        String result = builder.toString();
        Log.e("xxxx", result);

        return result;
    }

    public int getSize() {
        return size;
    }

    static class Node {
        Node next;
        String data;

        public Node(String data) {
            this.data = data;
        }
    }
}

• 实现LRUCache

public class LRUCache {
    LinkedList list = new LinkedList();

    int max = 5;


    /**
     * 设置最大缓存数量
     *
     * @param max
     */
    public LRUCache(int max) {
        this.max = max;
    }

    /**
     * 从链表中查询数据，
     * 如果有数据，则将该数据插入链表头部并删除原数据
     *
     * @param data
     * @return
     */
    public String get(String data) {
        String result = list.getNode(data);
        if (!TextUtils.isEmpty(result)) {
            list.removeNode(data);
            list.addFirst(data);
            return result;
        }
        return null;
    }

    /**
     * 数据在链表中是否存在？
     * 存在，将其删除，然后插入链表头部
     * 不存在，缓存是否满了？
     * 满了，删除链表尾结点，将数据插入链表头部
     * 未满，直接将数据插入链表头部
     * 时间复杂度O(n)
     * @param data
     */
    public void put(String data) {
        boolean exit = list.removeNode(data);
        if (exit) {
            list.addFirst(data);
        } else {
            if (list.getSize() < max) {
                list.addFirst(data);
            } else {
                list.removeLast();
                list.addFirst(data);
            }
        }
    }

    public String getAllCache() {
        return list.getLinkedList();
    }
}

• 具体使用

public class LruCacheActivity extends AppCompatActivity {

    TextView content;
    Button add,remove;
    EditText editText;
    LRUCache cache;
    Context context;
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_lru_cache);
        content = findViewById(R.id.tv_content);
        add = findViewById(R.id.add);
        remove = findViewById(R.id.remove);
        editText = findViewById(R.id.editText);
        context = this;
        cache = new LRUCache(5);
        add.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                //向缓存中增加一条数据
                cache.put(editText.getText().toString());
                content.setText(cache.getAllCache());
                editText.setText("");
            }
        });

        remove.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                //从缓存中查找数据
                String data = cache.get(editText.getText().toString());
                if(TextUtils.isEmpty(data)){
                    Toast.makeText(context,"未找到数据",Toast.LENGTH_SHORT).show();
                }else {
                    content.setText(cache.getAllCache());
                    Toast.makeText(context,"找到数据"+data,Toast.LENGTH_SHORT).show();
                }
                editText.setText("");
            }
        });
    }
}

没啥说的，具体都在注释里了！