Linkedlist是一个集合容器,具有增删改查基本功能,本例中模拟增删查,对于修改,只需要将原节点处的val更新为新值即可,增加和删除在链表中速度是比较快的,查找,修改慢,因为要从头或者从尾开始遍历。自定义的linkedList名称为yLinkedList。
类似于ArrayList中需要有一个数组来存储元素,在Linkedlist中也需要一个容器来存储元素,这个容器叫什么名字自己随意取,这里使用Node。该容器理论上可以放在任意处,只要在Mylinkedlist中可以调用即可,但考虑到外部类不会直接使用Node,所以将Node作为Mylinkedlist的内部私有类比较合适。
链表有长度,所以具有属性size,链表通过索引查找元素时,从头部或者尾部开始遍历,链表中需要存在头部(head)和尾部(tail)节点,LinkedList是双链表,在每个Node节点中都需要存在一个指向前一个节点指针和指向后一个节点指针,且Node节点也必须保存当前节点的值,这样MyLinkedList的大致结构就有了,由于是简单模拟增删查,List接口中的方法挺多的,故未实现List
package com.demo.langdemo.jdk; public class MyLinkedList { int size; // 当前集合的首节点 private Node head; // 当前集合的尾节点 private Node tail; /* * 存储元素的容器 */ private class Node { // 当前节点的值 Object val; // 当前节点的前一个节点 Node pre; // 当前节点的后一个节点 Node next; Node(Node pre, Object val, Node next) { this.pre = pre; this.val = val; this.next = next; } } }
在首部添加元素
当前添加的元素的前一个节点是null,后一个节点就是之前的head节点,若当前的首节点为null,则表明整个集合元素个数为0,,将当前元素添加后,首尾节点相同,都为当前节点。当首节点不为null,则将当前首节点的的pre指向新添加节点,并且将首节点指向新添加节点
public void addFirst(Object val) { // 定位新添加的节点的位置,添加到首节点,则其前驱节点为null Node newNode = new Node(null, val, head); // 修改其他节点位置 if (head == null) { // 首节点为空,则说明当前集合中还不存在数据,尾节点为空,也说明为空,但两个判断条件同样效果,使用一个判断即可 tail = newNode; } else { head.pre = newNode; } // 更新head为当前节点 head = newNode; size++; }
在尾部添加元素
在尾部添加元素时,前一个节点即为尾节点,后一个节点为null,当尾节点为null时,则表明整个集合元素个数为0,此时首尾节点相同,都为当前节点。当尾节点不为null时,将当前尾节点的的next指向新添加节点,并且将tail节点指向新添加元素
public void addLast(Object val) { // 定位新添加的节点的位置,添加到尾节点,则其后继节点为null Node newNode = new Node(head, val, null); if (tail == null) { // 尾节点为空 head = newNode; } else { tail.next = newNode; } tail = newNode; size++; }
直接调用add方法时,从头插入或者从尾插入可根据具体情况选择
在指定位置添加元素
首先确定索引是否超出了当前集合的size,超出则抛出异常,如果index==size,则在尾部插入,如果index==0,则在头部插入,否则即是在中间部位插入。中间部位插入时,首先要获取到查入位置已存在的节点(查询方法在后面介绍),获取其pre节点,新添加节点的pre指向已存在节点的pre节点,新添加节点的next节点指向已经存在的已存在的节点。已存在的节点的pre节点的next节点指向新添加节点,已存在的节点的pre节点指向新添加节点
public void add(int index, Object val) { // 需要找到当前索引的节点 try { if (index < 0 || index > size) { throw new Exception("error"); } } catch (Exception e) { e.printStackTrace(); } if (index == size) { addLast(val); } else if (index == 0) { addFirst(val); } else { Node currNode = getNode(index); Node pre = currNode.pre; Node newNode = new Node(pre, val, currNode); pre.next = newNode; currNode.pre = newNode;
size ++; } }
查找指定位置的节点
从中间开始查找无从下手,但每次添加元素时,size都会做对应的自增,所以每个索引也是唯一对应一个元素的,这里不考虑性能,直接就从head开始遍历查找,找index对应元素,那么index-1的next节点即为当前要找的index对应的元素
public Object get(int index) { return getNode(index).val; } private Node getNode(int index) { Node node = head; for (int i = 0; i < index; i++) { // 将head的next节点重新赋值给node,继续查询下一个head的next节点,这样,index-1的next节点即为我们所需要的节点 node = head.next; } return node; }
根据指定索引删除
获取索引对应的元素,找到其pre和next节点,并将pre和next节点之间建立联系,将当前被删除元素的pre和next节点置为null,解除与集合中元素的联系
public Object remove(int index) { // 找到索引对应的节点 Node node = getNode(index); // 获取该节点的pre和next节点 Node pre = node.pre; Node next = node.next; // 设置该节点的pre和next对应关系 pre.next = next; next.pre = pre; node.next=null; node.pre = null; size--; return node.val; }
根据元素值删除
从头或者从尾或者两头开始遍历等,扎到每个node节点的值与要删除的对比,若一致,则删除,将当前要删除的节点的pre和next节点删除,解除与集合中元素的关系,注意要删除的元素必须是重写了equals方法,否则删除的结果可能与预期不一致。
public Object remove(Object val) { Node node = head; for (int i = 0; i < size; i++) { if (node.val.equals(val)) { Node pre = node.pre; Node next = node.next; pre.next = next; next.pre = pre; break; } node = node.next; } node.pre = null; node.next = null; size--; return node.val; }
完整实现类
MyLinkedList.java
package com.demo.langdemo.jdk; public class MyLinkedList { int size; // 当前集合的首节点 private Node head; // 当前集合的尾节点 private Node tail; /* * 存储元素的容器 */ private class Node { // 当前节点的值 Object val; // 当前节点的前一个节点 Node pre; // 当前节点的后一个节点 Node next; Node(Node pre, Object val, Node next) { this.pre = pre; this.val = val; this.next = next; } } public void addLast(Object val) { // 定位新添加的节点的位置,添加到尾节点,则其后继节点为null Node newNode = new Node(head, val, null); if (tail == null) { // 尾节点为空 head = newNode; } else { tail.next = newNode; } tail = newNode; size++; } public void addFirst(Object val) { // 定位新添加的节点的位置,添加到首节点,则其前驱节点为null Node newNode = new Node(null, val, head); // 修改其他节点位置 if (head == null) { // 首节点为空,则说明当前集合中还不存在数据,尾节点为空,也说明为空,但两个判断条件同样效果,使用一个判断即可 tail = newNode; } else { head.pre = newNode; } // 更新head为当前节点 head = newNode; size++; } public void add(Object val) { // addFirst(val); addLast(val); } public Object get(int index) { return getNode(index).val; } private Node getNode(int index) { Node node = head; for (int i = 0; i < index; i++) { // 将head的next节点重新赋值给node,继续查询下一个head的next节点,这样,index-1的next节点即为我们所需要的节点 node = head.next; } return node; } public String toString() { StringBuilder str = new StringBuilder(); Node node = head; while (node != null) { str.append(node.val).append(","); node = node.next; } return str.deleteCharAt(str.length() - 1).toString(); } public void add(int index, Object val) { // 需要找到当前索引的节点 try { if (index < 0 || index > size) { throw new Exception("error"); } } catch (Exception e) { e.printStackTrace(); } if (index == size) { addLast(val); } else if (index == 0) { addFirst(val); } else { Node currNode = getNode(index); Node pre = currNode.pre; Node newNode = new Node(pre, val, currNode); pre.next = newNode; currNode.pre = newNode; size++; } } public Object remove(int index) { // 找到索引对应的节点 Node node = getNode(index); // 获取该节点的pre和next节点 Node pre = node.pre; Node next = node.next; // 设置该节点的pre和next对应关系 pre.next = next; next.pre = pre; node.next = null; node.pre = null; size--; return node.val; } public Object remove(Object val) { Node node = head; for (int i = 0; i < size; i++) { if (node.val.equals(val)) { Node pre = node.pre; Node next = node.next; pre.next = next; next.pre = pre; break; } node = node.next; } node.pre = null; node.next = null; size--; return node.val; } public int getSize() { return size; } }
在本次模拟中,未考虑性能等问题,只是实现了简单的功能,了解下链表的结构及实现思路。还需要查看大神写的LinkedList源码,了解其实现精髓。
ArrayList和LinkedList,前者查询和修改快,添加和删除慢,后者是查询,修改慢,添加删除快。