在双向链表中,除了下一个节点链接之外,每个节点还包含指向序列中“前
一个”节点的第二个链接字段。这两个链接可以称为'forward('s')和'backwards',
或'next'和'prev'('previous')。如图所示
以下通过Java语言手写实现LinkedList。包结构如下
package linked_list1; /** * @author cv master * @date 2022/11/18 9:25 */ public interface List<E> { boolean add(E e); boolean addFirst(E e); boolean addLast(E e); boolean remove(Object o); E get(int index); void PrintLinkList(); }
package linked_list1; /** * @author cv master * @date 2022/11/28 22:26 */ public class LinkedList<E> implements List<E> { transient Node<E> first; transient Node<E> last; transient int size; public LinkedList() { } private static class Node<E> { Node<E> prev; E item; Node<E> next; public Node(Node<E> prev, E item, Node<E> next) { this.prev = prev; this.item = item; this.next = next; } } @Override public boolean add(E e) { linkLast(e); return true; } @Override public boolean addFirst(E e) { linkFirst(e); return true; } @Override public boolean addLast(E e) { return false; } void linkLast(E e) { Node<E> l = last; Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) { first = newNode; } else { l.next = newNode; } } void linkFirst(E e) { Node<E> f = first; Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) { last = newNode; } else { f.prev = newNode; } } @Override public boolean remove(Object o) { if (null == o) { for (Node<E> x = first; x != null; x = x.next) { if (null == x.item) { unlink(x); } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); } } } return true; } E unlink(Node<E> x) { Node<E> next = x.next; E element = x.item; Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; } if (next == null) { last = prev; } else { next.prev = prev; } return element; } @Override public E get(int index) { return node(index).item; } Node<E> node(int index) { Node<E> x; if (index < (size >> 1)) { x = first; for (int i = 0; i < index; i++) { x = x.next; } } else { x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } } return x; } @Override public void PrintLinkList() { System.out.print("链表的头节点是:"+first.item+" 链表的尾节点是:"+last.item+" 整体为:"); Node<E>x=first; while (x!=null){ System.out.print(x.item+". "); x=x.next; } System.out.println(); } }
其中的linkFirst是头插的操作,先把旧的头节点记录下来,之后创建一个新的节点,新的节点的构造函数的prev为null,通过这样的方式构造一个新的头节点。
旧的头节点,设置f.prev连接到新的节点。
另外,如果没有头节点,头节点设置为新的节点即可。最后记录链表的节点数量size。
尾插法linkLast与头插法正好相反,先把旧的尾节点保留下来,构造新的尾节点,并把旧的尾节点,通过l.next关联到新的尾节点上。同时记录size的变化。
测试类:
package linked_list1; /** * @author cv master * @date 2022/11/29 15:25 */ public class LinkedListTest { public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.add(1); linkedList.addFirst(3); linkedList.remove(3); linkedList.PrintLinkList(); } }
标签:Node,null,next,链表,public,双向,prev,节点 From: https://www.cnblogs.com/luorongxin/p/16932594.html