何为链表
链式结构是一种使用对象引用变量来创建对象间的链的数据结构。
对象引用变量可用于创建链式结构
对象引用变量所存储的特定地址一般无关紧要。换句话说，重要的是能够使用引用变量来访问对象，而对象在内存中的特定存储位置并不重要。因此，我们一般将引用变量描述为一个“指向”对象的名称，而不是显示其地址，按照这种理解，引用变量有时称为“指针”
下面的这个类就是一个链式结构：
123456 |
public class Person { private String name; private String address;
private Person next; // Person对象的引用}
|
这种类型的对象有时称为自引用对象。
这种关系构成了链表的基础。链表是一种链式结构，该结构中的每个对象都指向下一个对象，从而构成了链表中对象的线性次序。。链表中存储的对象一般称为链表的节点。
注意，链表单独需要一个引用变量，用以表示其第一个结点。如果某个结点的next引用为null，则表示链表在该结点处终止
实现一个单向链表
插入结点
可能会在链表的任何位置插入一个结点：在链表的首部，或在链表中任何内部结点之间，或在链表的尾部。
（1）在首部插入结点
第一步，设置所添加结点的next引用，使其指向链表中当前的第一个结点。
第二步，重新设置指向链表首部的引用，使其指向这个新添加的结点。
注意：如果上述这些步骤颠倒了，则将会遇到困难。如果首先重置front引用，则将失去这个唯一指向现有链表的引用，而且再也不能获取它。
（2）在其他部分插入结点
首先，设置新节点的next引用，使其指向current锁引用结点的下一个结点。然后，重新设置当前结点的next引用，使其指向这个新的结点。
删除结点
对链表中的第一个结点的处理一般也比较特殊。
要删除链表的第一个结点，则要重新设置指向链表首部的引用，使其指向链表中当前的第二个结点。
一旦找到索要删除的结点，则重新设置前一个结点的next引用，使其指向的结点与当前结点的next引用所指向的结点相同。然后，可以根据需要使用这个删除的结点。
代码实现
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210 |
package chain;
/** * Created by benjamin on 1/18/16. * 单向链表的实现 */public class NodeList<E> {
private static class Node<E> { E data; Node<E> next; public Node(E data, Node<E> next) { this.data = data; this.next = next; } }
/** 首元素的引用 **/ private Node<E> head;
/** 尾元素的引用 **/ private Node<E> last;
/** 其他元素的引用 **/ private Node<E> other;
/** list的元素个数 **/ private int size = 0;
/** * 默认构造 */ public NodeList() { head = null; last = head; }
/** * 构造一个有参数的list * @param data 初始化参数 */ public NodeList(E data) { Node<E> d = new Node<>(data, null); head = d; last = head; size++; }
/** * 增加一个数据到list中 * @param data 新增的数据 */ public void add(E data) { Node<E> 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<E> d = new Node<>(data, other); head = d; } else { for (int i = 0; i < index; i++) { other = other.next; } Node<E> 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<E> 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<E> 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<String> 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 链表为空 */ }}
|
上面只是单向链表的简单实现。
实现一个双向链表
链式结构的另一种实现就是双向链表。双向链表维护两个引用：一个指向链表的第一个结点，另一个指向最后一个结点。链表中的每个结点都存储两个引用：一个指向下一个结点，另一个指向前一个结点。
下面是我仿着LinkedList写的双向链表。自己写完后发现很多地方原作者写的真是精妙，把增加元素、移除元素抽离出来，以及写法的精简、效率的考虑（利用索引构造结点处判断index是否小于size>>1），自己受益匪浅。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409 |
package chain;
import java.io.Serializable;import java.util.NoSuchElementException;
/** * Created by benjamin on 1/18/16. */public class LinkedList<E> implements Serializable {
private static final long serialVersionUID = -5635851059340344485L;
/** * 结点类 * @param <E> */ private static class Node<E> { E item; Node<E> next; Node<E> prev;
Node(Node<E> prev, E item, Node<E> next) { this.prev = prev; this.item = item; this.next = next; } }
/** 第一个结点的引用 **/ transient Node<E> first;
/** 最后一个结点的引用 **/ transient Node<E> last;
/** list中元素的数目 **/ transient int size = 0;
/** 操作次数 **/ transient int modCount = 0;
public LinkedList() { }
/** * 把传入的元素变为第一个元素 * @param e */ private void linkFirst(E e) { Node<E> f = first; Node<E> 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<E> l = last; Node<E> 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<E> succ) { final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
/** * 取消第一个结点的引用 */ private E unlinkFirst(Node<E> f) { final E element = f.item; final Node<E> 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<E> l) { final E element = l.item; final Node<E> 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<E> x) { final E element = x.item; final Node<E> next = x.next; final Node<E> 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<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }
/** * 取得最后一个元素 * @return 最后一个元素 */ public E getLast() { final Node<E> l = last; if (last == null) throw new NoSuchElementException(); return l.item; }
/** * 删除第一个元素 * @return 第一个被删除的元素 */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
/** * 删除最后一个元素 * @return 最后一个被删除的元素 */ public E removeLast() { final Node<E> 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<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> 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<E> x = first; x != null; ) { Node<E> 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<E> 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<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> 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<E> node(int index) {
// 如果是大小的一半之前,正序查找,否则倒序查找,提高效率 if (index < (size >> 1)) { Node<E> f = first; for (int i = 0; i < index; i++) f = f.next; return f; } else { Node<E> 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; }}
|
时间： 2024-09-20 18:21:57