# Java实现单向双向链表原理分析

### 何为链表

 123456 public class Person { private String name; private String address; private Person next; // Person对象的引用}

### 实现一个单向链表

（1）在首部插入结点

（2）在其他部分插入结点

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210 package chain;/** * Created by benjamin on 1/18/16. * 单向链表的实现 */public class NodeList { private static class Node { E data; Node next; public Node(E data, Node next) { this.data = data; this.next = next; } } /** 首元素的引用 **/ private Node head; /** 尾元素的引用 **/ private Node last; /** 其他元素的引用 **/ private Node other; /** list的元素个数 **/ private int size = 0; /** * 默认构造 */ public NodeList() { head = null; last = head; } /** * 构造一个有参数的list * @param data 初始化参数 */ public NodeList(E data) { Node d = new Node<>(data, null); head = d; last = head; size++; } /** * 增加一个数据到list中 * @param data 新增的数据 */ public void add(E data) { Node d = new Node<>(data, null); if (isEmpty()) { head = d; last = head; } else { last.next = d; last = d; } size++; } /** * 在index处添加元素data,其他元素后移 * @param index 元素索引,从0开始. * @param data 新增元素 */ public void add(int index, E data) { checkIndex(index); other = head; if (index == 0) { //如果加在第一个,就把head的引用设为新元素对象 Node d = new Node<>(data, other); head = d; } else { for (int i = 0; i < index; i++) { other = other.next; } Node d = new Node<>(data, other.next); other.next = d; } size++; } /** * 替换原有的值为newValue * @param oldValue 旧值 * @param newValue 新值 * @return 如果替换成功返回true, 否则返回false */ public boolean set(E oldValue, E newValue) { other = head; while (other != null) { if (other.data.equals(oldValue)) { other.data = newValue; return true; } other = other.next; } return false; } /** * 在指定的值后面插入一个新值 * @param specidiedData 指定的值 * @param newData 新值 * @return 如果插入成功返回true,否则返回false */ public boolean addAfter(E specidiedData, E newData) { other = head; while (other != null) { if (other.data.equals(specidiedData)) { Node d = new Node<>(newData, other.next); other.next = d; size++; return true; } other = other.next; } return false; } /** * 根据索引, 获得此处的数据 * @param index 索引 * @return 获得的数据 */ public E get(int index) { checkIndex(index); other = head; for (int i = 0; i < index; i ++) { other = other.next; } return other.data; } /** * 删除list中存在的data * @param data 要删除的数据 * @return 如果删除成功返回true,否则返回false */ public boolean remove(E data) { other = head; Node pre = other; for (int i = 0; i < size; i++) { if (other.data.equals(data)) { if (i == 0) { head = other.next; return true; } pre.next = other.next; return true; } pre = other; other = other.next; } return false; } /** * 是否包含传入的元素 * @param data 传入的数据 * @return 如果存在返回true, 否则false */ public boolean contains(E data) { other = head; for (int i = 0; i < size; i++) { if (other.data.equals(data)) { return true; } } return false; } private boolean isEmpty() { return size == 0 || head == null; } /** * 清空链表 */ public void clear() { head = null; size = 0; } public void checkIndex(int index) { if (index < 0 || index > size-1) throw new IndexOutOfBoundsException("传入的索引无效: " + index); } /** * 打印全部链表数据 */ public void print() { if (head == null || size == 0) System.out.println("链表为空"); else { other = head; while (other != null) { System.out.print(other.data + " "); other = other.next; } System.out.println(); } }}
 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 package chain;/** * Created by piqiu on 1/18/16. */public class NodeListTest { public static void main(String[] args) { NodeList nodeList = new NodeList<>("first"); nodeList.add("a"); nodeList.add("b"); nodeList.add("c"); nodeList.print(); nodeList.add(2, "addNew"); nodeList.print(); nodeList.set("c", "C"); nodeList.print(); nodeList.addAfter("addNew", "addNew2"); nodeList.print(); System.out.println(nodeList.get(2)); nodeList.remove("addNew2"); nodeList.print(); nodeList.remove("first"); nodeList.print(); System.out.println(nodeList.contains("a")); System.out.println(nodeList.contains("A")); nodeList.clear(); nodeList.print(); /** * first a b c first a b addNew c first a b addNew C first a b addNew addNew2 C b first a b addNew C a b addNew C true false 链表为空 */ }}

### 实现一个双向链表

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409 package chain;import java.io.Serializable;import java.util.NoSuchElementException;/** * Created by benjamin on 1/18/16. */public class LinkedList implements Serializable { private static final long serialVersionUID = -5635851059340344485L; /** * 结点类 * @param */ private static class Node { E item; Node next; Node prev; Node(Node prev, E item, Node next) { this.prev = prev; this.item = item; this.next = next; } } /** 第一个结点的引用 **/ transient Node first; /** 最后一个结点的引用 **/ transient Node last; /** list中元素的数目 **/ transient int size = 0; /** 操作次数 **/ transient int modCount = 0; public LinkedList() { } /** * 把传入的元素变为第一个元素 * @param e */ private void linkFirst(E e) { Node f = first; Node newNode = new Node<>(null, e, f); if (f == null) last = newNode; else f.prev = newNode; first = newNode; size++; modCount++; } /** * 在最后面插入元素 * @param e */ private void linkLast(E e) { Node l = last; Node newNode = new Node<>(l, e, null); if (l == null) first = newNode; else l.next = newNode; last = newNode; size++; modCount++; } /** * 在指定结点之前插入元素 * @param e * @param succ 指定结点 */ private void linkBefore(E e, Node succ) { final Node pred = succ.prev; final Node newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } /** * 取消第一个结点的引用 */ private E unlinkFirst(Node f) { final E element = f.item; final Node next = f.next; f.item = null; f.next = null; first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } /** * 取消最后一个结点的引用 * @param l * @return 最后一个结点的值 */ private E unlinkLast(Node l) { final E element = l.item; final Node pred = l.prev; l.item = null; l.prev = null; last = pred; if (pred == null) first = null; else pred.next = null; size--; modCount++; return element; } /** * 取消结点x的引用 * @param x * @return 取消的结点元素 */ E unlink(Node x) { final E element = x.item; final Node next = x.next; final Node pred = x.prev; // 如果是第一个 if (pred == null) first = next; else { pred.next = next; x.prev = null; } //如果是最后一个 if (next == null) last = pred; else { next.prev = pred; x.next = null; } x.item = null; size--; modCount++; return element; } /** * 取得第一个元素 * @return 第一个元素 */ public E getFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * 取得最后一个元素 * @return 最后一个元素 */ public E getLast() { final Node l = last; if (last == null) throw new NoSuchElementException(); return l.item; } /** * 删除第一个元素 * @return 第一个被删除的元素 */ public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * 删除最后一个元素 * @return 最后一个被删除的元素 */ public E removeLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * 增加一个元素到list的第一个位置 * @param e */ public void addFirst(E e) { linkFirst(e); } /** * 增加一个元素到list的结尾 * @param e */ public void addLast(E e) { linkLast(e); } /** * 增加一个元素(默认增加在结尾) * @param e * @return true */ public boolean add(E e) { linkLast(e); return true; } /** * 删除list中存在传入的对象 * @param o * @return 如果改变了list,返回true,否则false */ public boolean remove(Object o) { if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /** * 清空list,所有引用对象置为null */ public void clear() { for (Node x = first; x != null; ) { Node next = x.next; x.item = null; x.prev = null; x.next = null; x = next; } first = null; last = null; size = 0; modCount++; } /** * 获取索引处的元素值 * @param index 索引 * @return 元素值 */ public E get(int index) { checkIndex(index); return node(index).item; } /** * 替换索引处的值为element * @param index 索引 * @param element 新值 * @return 旧值 */ public E set(int index, E element) { checkIndex(index); Node oldNode = node(index); E oldValue = oldNode.item; oldNode.item = element; return oldValue; } /** * 在指定索引的地方插入元素element,原来的元素以及之后的元素后移 * @param index 插入元素的索引 * @param element 插入的元素 */ public void add(int index, E element) { checkIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } /** * 移除索引处的元素 * @param index 索引 * @return 删除的元素 */ public E remove(int index) { checkIndex(index); return unlink(node(index)); } /** * 获取对象在list中的索引 * @param o 要查找的对象 * @return 如果找到了对象,返回对应的索引值,否则返回-1 */ public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } /** * 是否包含元素 * @param o * @return 如果包含返回true */ public boolean contains(Object o) { return indexOf(o) != -1; } /** * 返回list中元素的大小 * @return 元素的大小 */ public int getSize() { return size; } /** * 根据索引得到结点 * @param index 索引 * @return 结点 */ Node node(int index) { // 如果是大小的一半之前,正序查找,否则倒序查找,提高效率 if (index < (size >> 1)) { Node f = first; for (int i = 0; i < index; i++) f = f.next; return f; } else { Node l = last; for (int i = size - 1; i > index; i--) l = l.prev; return l; } } /** * 检查索引是否正确,不正确抛出 IndexOutOfBoundsException 异常 * @param index */ private void checkIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 越界的错误信息 * @param index 越界的错误索引 * @return 越界的msg */ private String outOfBoundsMsg(int index) { return "Index: " + index + ", Size: " + size; } /** * 检查索引是否没有溢出 * @param index 索引 * @return 如果索引正确返回true */ private boolean isElementIndex(int index) { return index >= 0 && index < size; }}

|
1天前
|
Java 数据库连接 Spring
K8S+Docker理论与实践深度集成java面试jvm原理
K8S+Docker理论与实践深度集成java面试jvm原理
6 1
|
2天前
|
Java 关系型数据库 MySQL
【Java Spring开源项目】新蜂(NeeBee)商城项目运行、分析、总结
【Java Spring开源项目】新蜂(NeeBee)商城项目运行、分析、总结
13 4
|
2天前
|
Java
【Java多线程】分析线程加锁导致的死锁问题以及解决方案
【Java多线程】分析线程加锁导致的死锁问题以及解决方案
25 1
|
2天前
|

24 0
|
2天前
|

JVM工作原理与实战(十六)：运行时数据区-Java虚拟机栈
JVM作为Java程序的运行环境，其负责解释和执行字节码，管理内存，确保安全，支持多线程和提供性能监控工具，以及确保程序的跨平台运行。本文主要介绍了运行时数据区、Java虚拟机栈等内容。
12 0
|
2天前
|

8大Java排序方法(由简入繁)，有代码详解和原理指导
8大Java排序方法(由简入繁)，有代码详解和原理指导
33 0
|
2天前
|
Java
JAVA循环结构分析与设计
JAVA循环结构分析与设计
20 1
|
2天前
|

【Java EE】CAS原理和实现以及JUC中常见的类的使用
【Java EE】CAS原理和实现以及JUC中常见的类的使用
10 3
|
2天前
|

【专栏】介绍了字符串Base64编解码的基本原理和在Java、Python、C++、JavaScript及Go等编程语言中的实现示例
【4月更文挑战第29天】本文介绍了字符串Base64编解码的基本原理和在Java、Python、C++、JavaScript及Go等编程语言中的实现示例。Base64编码将24位二进制数据转换为32位可打印字符，用“=”作填充。文中展示了各语言的编码解码代码，帮助开发者理解并应用于实际项目。
23 1
|
2天前
|

Java排序：原理、实现与应用
【4月更文挑战第28天】本文探讨了Java中的排序算法，包括原理和实现。Java利用Comparator接口进行元素比较，通过Arrays和Collections类的sort方法对数组和列表进行排序。示例展示了使用这些方法的基本代码。此外，还讨论了冒泡排序算法和自定义排序场景，以适应不同需求。理解这些排序机制有助于提升程序效率。
13 1