定义
- 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的；
- 链表由多个链结点组成，每个链结点由两部分组成，一个存储数据元素的数据域，一个存储下一个结点地址的指针域；
- 在链表中，寻找一个特定元素的唯一方法，就是沿着这个元素的链一直向下寻找；
解决的问题
无序数组搜索慢，有序数组插入慢，且数组的删除效率低，大小固定；
链表则常用来替换数组，作为其他存储结构的基础，以解决上面问题；
除非需要频繁的用下标随机访问各个数据，否则很多地方都可以用链表代替数组。
分类：
- 单链表
- 双端链表
- 有序链表
- 双向链表
- 有迭代器的链表
单链表的实现（含迭代器）
- 创建一个链结点类
public class Link<T> {
public T data;//数据域
public Link<T> next;//指针域, 指向下一个链结点
//此处next为一个和自己类型相同的字段，因此也叫"自引用"式
public Link(T data) {
this.data = data;
}
public void display(){
System.out.print("Link:{"+data.toString()+"}");
}
}
- 单链表实现类, 其中一些关键的地方都有注释，这里就不再多说了，
public class LinkList<T> {
protected Link<T> first;//LinkList仅包含了一个数据项，即对第一个链结点的引用
public boolean isEmpty() {
return first == null;
}
/**
* 向链表插入数据
*
* @param value
*/
public void insertFirst(T value) {
//新建链结点，把数据传入这个链结点，将这个新的链结点的next字段指向原来的first的值，将first指向这个新的链结点
Link<T> newLink = new Link<>(value);
newLink.next = first;
first = newLink;
}
public Link<T> deleteFirst() {
Link temp = first;
first = first.next;
return temp;
}
public void display() {
System.out.print("LinkList:{ ");
Link current = first;
while (current != null) {
current.display();
if (current.next != null)
System.out.print(", ");
current = current.next;
}
System.out.println("} ");
}
public Link<T> find(T value) {
Link current = first;
//找到才跳出循环，否则一直找，直到next==null，该链结点链表的最后一个
while (!current.data.equals(value)) {
if (current.next == null)
return null;
else
current = current.next;
}
return current;
}
public Link<T> delete(T value) {
Link current = first;//当前链结点
Link previous = first;//当前值的前一个链结点
if (current == null)
return null;
//找到才跳出循环，否则一直找，直到next==null，该链结点链表的最后一个
while (!current.data.equals(value)) {
if (current.next == null)
return null;
else {
previous = current;
current = current.next;
}
}
if (current == first)
//如果所找的值对应first链结点，就把first指向下一个链结点，也就是first.next
first = first.next;
else
//如果不是对应first，就把该链结点的前一个链结点的指针next指向该链结点的下一个链结点，即current.next
previous.next = current.next;
return current;
}
public LinkIterator<T> iterator(){
return new LinkIterator<>(this);
}
public Link<T> getFirst() {
return first;
}
}
上面的LinkIterator迭代器类的实现如下：
public class LinkIterator<T> {
private LinkList<T> linkList;
private Link<T> current;
private Link<T> previous;
public LinkIterator(LinkList<T> linkList) {
this.linkList = linkList;
reset();
}
private void reset() {
current=linkList.getFirst();
previous=null;
}
public Link<T> getCurrent() {
return current;
}
public boolean hasNext(){
return current!=null&¤t.next!=null;
}
public Link<T> next(){
previous=current;
current=current.next;
return previous;
}
public void remove(){
if (current==linkList.first)
linkList.first=linkList.first.next;
else
previous.next=current.next;
}
}
- 对单链表实现类的使用
private static void testLinkList() {
LinkList<String> linkList = new LinkList<>();
for (int i = 0; i < 10; i++) {
linkList.insertFirst("data_" + i);
linkList.display();
}
linkList.find("data_3").display();
linkList.delete("data_5").display();
linkList.delete("data_7").display();
linkList.delete("data_8").display();
linkList.display();
}
- 迭代器的使用
private static void testLinkIterator() {
LinkList<String> linkList = new LinkList<>();
for (int i = 0; i < 10; i++) {
linkList.insertFirst("data_" + i);
linkList.display();
}
System.out.println("----> iterator:");
LinkIterator<String> iterator = linkList.iterator();
while (iterator.hasNext()) {
Link<String> link = iterator.getCurrent();
link.display();
System.out.println();
if (link.data.equals("data_6")) {
iterator.remove();
}
iterator.next();
}
linkList.display();
}
- 之前介绍栈时有提到可以使用链表实现：将ArrayStack中的数组替换为LinkList，push用insertFirst实现，pop用deleteFirst实现，也是完全可以的，实现代码如下：
public class LinkStack<T> extends Stack<T> {
private LinkList<T> linkList;
public LinkStack() {
linkList =new LinkList();
}
@Override
public boolean isEmpty() {
return linkList.getFirst()==null;
}
@Override
public void push(T value) {
linkList.insertFirst(value);
}
@Override
public T pop() {
return linkList.deleteFirst().data;
}
@Override
public T peek() {
return linkList.getFirst().data;
}
@Override
public void display() {
System.out.print("LinkStacker: ");
linkList.display();
}
}
有序链表
- 数据项按照关键值有序排列
- 之前有用有序数组实现优先级队列，然而使用有序链表也是可以实现的
- 提供一种新的数组排序算法：表插入排序
有序链表可以用于一种高效的排序机制，假设有一个无序数组，如果从这个数组中取出数据，然后一个一个的插入有序链表，他们自动的按顺序排列，把它们从有序表中删除，重新放入数组，那么数组就排好序了，这种排序方式比常用的插入排序效率更高些； - 那么为什么不直接用有序数组呢？有序链表的插入效率要优于有序数组，因为不需要移动元素；而且链表所占用内存是充分利用的，而且扩充方便，不用担心角标越界问题；
- 有序链表的实现
public class OrderedLinkList<T extends Comparable<T>> extends LinkList<T> {
public void insert(T value) {
Link<T> newLink = new Link<>(value);
Link<T> previous = null;
Link<T> current = first;
while (current != null && value.compareTo(current.data) > 0) {
previous = current;
current = current.next;
}
if (previous == null)
first = newLink;
else
previous.next = newLink;
newLink.next = current;
}
public Link<T> find(T value) {
Link<T> current = first;
while (current != null && current.data.compareTo(value) <= 0) {
if (current.data == value)
return current;
current = current.next;
}
return null;
}
public Link<T> delete(T value) {
Link<T> previous = null;//当前值的前一个链结点
Link<T> current = first;//当前链结点
while (current != null && current.data.compareTo(value) < 0) {
previous = current;
current = current.next;
}
if (current.data != value)
return null;
if (current == first)
//如果所找的值对应first链结点，就把first指向下一个链结点，也就是first.next
first = first.next;
else
//如果不是对应first，就把该链结点的前一个链结点的指针next指向该链结点的下一个链结点，即current.next
previous.next = current.next;
return current;
}
}
网友评论