手撕数据结构篇一（LinkedList）

题主java 开发5年，面试中经常被问到List,今天来归纳下我们获取用的不是那么多的linkedList，一起看看其内部结构到底长什么样子。

关于List 我们常用到的方法可能就是，add(), get(int index),或者remove... 常见的也就是add,get,再就是遍历了。常常听说各种面试资料里边说LinkedList 是链表结构，那传说中的链表结构到底长什么样子呢？今天说下题主自己的理解。

所谓链表，无非就是串起来的一组对象而已，众所周知，java 里边万物皆对象，那为什么我不直接用java 里边的对象呢？ 非要整一个链表将对象串起来？这里就不得不介绍下数据结构的作用了，链表提供了对对象的管理，方便api 使用方能很好的存储，并管理这些对象，假设没有链表，我们从数据库查出来的一组pojo 在内存中以什么形态存在呢？散落在内存各处，我们想遍历整个pojo或者想取某一个pojo 怎么得到呢？背景就介绍到这，接下来看代码实现（以下例子为个人按照linkedList 设计思路写的一个简版的linkedList）

package com.pingan.pastry.base;

import java.util.LinkedList;
import java.util.List;

public class MyLink<E> {

    private Note first;

    private int size;

    public MyLink() {
    }

    public MyLink(Note first, int size) {
        this.first = first;
        this.size = size;
    }

    public void add(E element) {
        add(size,element);

        /*if (first == null) {
            first = new Note(element, null);
            size++;
            return;
        } else {
            Note last = first;


        }
        size++;*/
    }


    public void add(int index, E element) {
        if (index == 0) {
            first = new Note(element, null);
        } else {
            Note<E> pre = getNote(index - 1);
            Note note = pre.next;

            pre.next = new Note<>(element, note);
        }
        size++;
    }

    private Note<E> getNote(int index) {
        Note note = first;
        for (int i = 0; i < index; i++) {
            note = note.next;
        }
        return note;
    }

    public E get(int index) {
        if (index >= 0 && index < size) {
            Note note = first;
            for (int i = 0; i < index; i++) {
                note = note.next;
            }
            return (E) note.getElement();
        } else {
            throw new IndexOutOfBoundsException("index： " + index + ",size: " + size);
        }
    }

    public void remove(Object v) {

    }

    class Note<E> {
        private E element;
        private Note next;

        public Note() {
        }

        public Note(E element, Note next) {
            this.element = element;
            this.next = next;
        }

        public E getElement() {
            return element;
        }

        public void setElement(E element) {
            this.element = element;
        }

        public Note getNext() {
            return next;
        }

        public void setNext(Note next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        List list=new LinkedList();
        MyLink linkData=new MyLink();
        linkData.add("hh");
        linkData.get(0);
        System.out.println("1: "+linkData.get(0));
        linkData.add(22);
        System.out.println("2 : "+linkData.get(1));
    }

输出结果：