编写自己的LinkedList

2019-11-06 07:36:28

字体：大中小

来源：转载

供稿：网友

今天我们来实现一下自己的LinkedList。首先设计底层数据结构双向链表在MyLinkedList类中创建一个内部类

PRivate class Node<E> { private E element; private Node<E> prev; private Node<E> next; public Node(Node<E> prev, E element, Node<E> next) { this.element = element; this.prev = prev; this.next = next; } }

然后该出关键的属性

// 代表链表的第一个元素 private Node<E> first; // 代表链表的最后一个元素 private Node<E> last; // 代表链表的长度 private int size = 0;

接下来设计MyLinkedList的构造函数，还是一样给出一个参数为空的构造函数和一个参数为包含指定 collection 中的元素的列表Collection

public MyLinkedList() { } public MyLinkedList(Collection<? extends E> c) { addAll(c); }

一般的，我们生成一个MyLinkedList有两种方式，一种是 List list=new MyLinkedList(); list.add(“kobe”); list.add(“james”); 那么我们来看一个add方法应该怎样实现分析，有上述代码，我们可以分析得出，链表的插入使用的尾插法

public boolean add(E element) { linkLast(element); return true; } public void linkLast(E e) { //先生成要插入链表的结点 //newNode.prev=last;newNode.next=null; //将newNode的prev指针指向之前的last结点 //next指向null， Node<E> newNode = new Node(last, e, null); //在这里我们需要判断一下last是否为null，也就是要判断newNode是否为第一个结点 if (last == null) { first = newNode; } else { //如果插入之前的链表不为空，将之前的last结点的next指向newNode last.next = newNode; } //last变为新插入的结点，这样便是尾插法 last = newNode; size++; }

另一种情况是直接用构造函数 public MyLinkedList(Collection

public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int num = a.length; if (num == 0) { return false; } Node<E> prev; Node<E> now; //在执行插入之前需要进行判断，因为有两种插入的情况，第一种是index==size,也就是说直接在尾部插入node(index)为null,lat=now.prev //另一种就是node(index)！=null if (index == size) { prev = last; now = null; } else { now = node(index); prev = now.prev; } for (Object obj : a) { @SuppressWarnings("unchecked") //先将Object类型转化为E,防止后续类型转化出错 E e = (E) obj; Node<E> newNode = new Node<E>(prev, e, null); //如果是要在首结点之前插入 if (prev == null) { //则有首结点为第一个新建的结点 first = newNode; } else { prev.next = newNode; } prev= newNode; } //现在最后一个新插入的结点指向null //判断now结点是否为空，如果是，则将最后一个新增结点记为last; if (now == null) { last = prev; } else { //如果不是null,将最后一个插入的结点和null结点链接起来 prev.next = now; now.prev = prev; } size += num; return true; }

看完add，我们再来看看remove

public boolean remove(Object obj) { // 因为LinkedList允许插入null值，所以这里要分两种情况 if (obj == null) { for (Node<E> result = first; result != null; result = result.next) { if (result.element == null) { unlink(result); return true; } } } else { for (Node<E> result = first; result != null; result = result.next) { if (result.element.equals(obj)) { return true; } } } return false; }public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; } private E unlink(Node<E> x) { E element = x.element; Node<E> prev = x.prev; Node<E> next = x.next; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.element = null; size--; return element; }

最后看一个Iteraotr接口的实现

上一篇：C语言深度解剖第一章笔记

下一篇：400. Nth Digit