链表
一个节点分两个部分，一部分存数据，一部分存下一个节点的内存地址
单项链表伪代码
LinkedList
- LInkedList是一个双向链表
- 源码分析：属性分析、构造方法分析、添加元素、修改元素、插入元素、删除元素
public class LinkelisrTest01 {public static void main(String[] args) {//双链表//空构造方法LinkedList<String> list1 = new LinkedList<>();list1.add("1");list1.add("2");list1.add("3");list1.add("4");list1.set(1,"110");list1.remove(1);String s = list1.get(list1.size() - 1);System.out.println(s);} }
属性分析
public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {transient int size = 0;/*** Pointer to first node.*/transient Node<E> first;/*** Pointer to last node.*/transient Node<E> last;存有头节点，尾节点，和链表的总节点数是一个双向链表
Node<E>是一个类，Node节点的含义，item保存的数据，next下一个节点的引用
private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev; }
构造方法
public LinkedList() {}
add()方法
先创建一个节点对象Node(),记录该节点的内存地址，前一个节点对象存储新节点的内存地址，新节点的prev存储前节点的内存地址，next存储后一个节点的内存地址，这样就增添了元素。
源码分析：
l保存的是上一个节点，new了一个新的节点，保存了l的内存地址和所要存储的数据，判断上一个节点是否位空，如果是空的话，则直接是头节点（注意first是一个头节点类，存储着size），如果不是，存储数量加1。
add(data,index)方法
源码分析
node（index）:根据下标找到节点
new一个新的节点，before保存新节点的地址，新节点保存before的地址，next保存下一个节点的地址。
set()方法
node（index）找到元素，直接改就行.
剩余两个类似，可以查看源码
手写单向链表
/*** 自定义单项链表*/ public class Test01<E> {//首先，有存储数据数量的方法private int size;private Node<E> first;/*** 无参构造方法*/public Test01() {}//获取集合中元素的个数public int size(){return size;}/*** 添加元素到末尾* @param data*/public void add(E data) {if (first == null) {first = new Node<>(data, null);size++;return;} else {//找到末尾节点Node<E> last = findLast();last.next = new Node<>(data, null);size++;}}/*** 寻找最后一个节点的方法* @return*/private Node<E> findLast() {if (first == null) {return null;} else {//假设第一个节点就是最后一个节点Node<E> last = first;while(last.next !=null){last = last.next;}return last;}}/*** 添加元素到指定的索引处* @param index* @param data*/public void add ( int index, E data){//创建新的节点对象Node<E> node = new Node<>(data,null);//找到对应下标节点Node<E> a = node(index);//新节点node next存储当前节点；node.next = a;//寻找当前下标节点的上一个节点Node<E> prev = node(index -1 );//上一个节点next值等于当前节点prev.next = node;}/*** 寻找指定节点的方法* @param index* @return*/private Node<E> node(int index) {Node<E> next =first;for (int i=0;i<index;i++){next = next.next;}return next;}/*** 删除元素* @param index*/public void remove (int index){Node<E> node = node(index);Node<E> prev = node(index-1);Node<E> next = node(index+1);prev.next = next;}/*** 修改元素* @param index* @param data*/public void set ( int index, E data){//寻找对应下标的nodeNode<E> node = node(index);node.item = data;}/*** 查找元素* @param index* @return*/public Node<E> get ( int index){Node<E> node = node(index);return node;}/*** 节点内部类* @param <E>*/private static class Node<E> {E item; //存储的数据值Node<E> next; //下一个节点public Node(E item, Node next) {this.item = item;this.next = next;}} }
