1.普通链表
链表结构的每个节点汇包含一个数据域和一个引用域,引用域直接存放下一个节点的地址.
如图所示:
- 代码示例
//链节点
public class Link {
private Link next; //下个节点
private String data; //数据
public Link(String data){
this.data = data;
}
public Link getNext() {
return next;
}
public void setNext(Link next) {
this.next = next;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
}
//链表
//链表也可以用first节点来表示
public class LinkList {
private Link first;
public LinkList() {
first = null;
}
//打印链表
public void display() {
if (first == null) {
System.out.println("LinkList is null");
return;
}
Link temp = first;
while (temp != null) {
System.out.print(temp.getData() + "-->");
temp = temp.getNext();
}
System.out.println();
}
//插入节点
public void insert(Link link) {
link.setNext(first);
first = link;
}
//删除节点
public void delete(String data){
Link pre = null;
Link temp = first;
while(temp != null){
if(data.equals(temp.getData())){
if(pre != null){
pre.setNext(temp.getNext());
}
//如果删除的是第一个节点，移动first
if(temp.equals(first)){
first = temp.getNext();
}
break;
}
pre = temp;
temp = temp.getNext();
}
this.display();
}
//查询节点
public Link query(String data) {
Link temp = first;
Link result = null;
while (temp != null) {
if (data.equals(temp.getData())) {
result = temp;
break;
}
temp = temp.getNext();
}
return result;
}
public static void main(String[] args) {
LinkList linkList = new LinkList();
//插入节点
linkList.insert(new Link("张三"));
linkList.insert(new Link("李四"));
linkList.insert(new Link("王五"));
linkList.insert(new Link("王五"));
//展示节点
linkList.display();
//查找节点
Link link = linkList.query("李四");
System.out.println(link.getData());
//删除节点
linkList.delete("张三");
}
}
输出:
王五-->王五-->李四-->张三-->
李四
王五-->王五-->李四-->
2.双端链表
first和last初始都为空,两端都可以插入,只有一个节点时,既是first也是last.
如图所示:
- 代码示例
//双端链表，头部尾部都可以插入删除
public class FirstLastLinkList {
private Link first;
private Link last;
public FirstLastLinkList() {
this.first = null;
this.last = null;
}
public Link getFirst() {
return first;
}
public void setFirst(Link first) {
this.first = first;
}
public Link getLast() {
return last;
}
public void setLast(Link last) {
this.last = last;
}
//打印链表
public void display() {
Link temp = first;
while (temp != null) {
System.out.print(temp.getData() + "-->");
temp = temp.getNext();
}
System.out.println();
}
//判空
public boolean isEmpty() {
return first == null;
}
//头部插入
public void insertFirst(Link link) {
link.setNext(first);
first = link;
//如果下个节点为空，则为尾部节点
if (link.getNext() == null) {
last = link;
}
}
//尾部删除
public void deleteLast() {
if (isEmpty()) {
return;
}
Link temp = first;
while (temp != null) {
if (temp.equals(last)) {
first = null;
last = null;
return;
}
if (temp.getNext().equals(last)) {
last = temp;
last.setNext(null);
return;
}
temp = temp.getNext();
}
}
public static void main(String[] args) {
FirstLastLinkList firstLastLinkList = new FirstLastLinkList();
//头部插入
firstLastLinkList.insertFirst(new Link("张三"));
firstLastLinkList.insertFirst(new Link("张三"));
firstLastLinkList.insertFirst(new Link("李四"));
firstLastLinkList.insertFirst(new Link("王五"));
firstLastLinkList.display();
//尾部删除
firstLastLinkList.deleteLast();
firstLastLinkList.display();
}
}
输出:
王五-->李四-->张三-->张三-->
王五-->李四-->张三-->
- 链表的效率
插入和删除 O(1)
查找O(N)
- 链表的优点
和数组相比,删除操作不需要节点的移动,效率有一定的提升.
另一个优点,链表的内存利用率高,有几个节点就占用多少内存,不需要指定节点数据.而数组需要预先开辟出一定长度的内存.虽然数组支持动态扩展,仍然是按比例的,比如长度为10扩展到20.
- 链表的缺点
链表相对数组的缺点:随机查找不方便.数组可以根据角标随机取出一个位置的数.而链表无法这么做,只能从头开始遍历.
- 链表的用途
普通链表实现栈,从first插入,从first取出即可,且理论上长度不限.
双端链表实现队列,从last插入,从first取出.很好地避免了用数组实现时的指针回绕问题.
有序链表可以用于实现优先级队列.
3.有序链表
节点在链表中依大小有序排列.
- 有序链表的优缺点
有序列表相对于有序数组的优点:
插入,删除效率较高,不用移动节点
内存利用率高.
- 有序链表的效率
删除O(1) 插入O(N)
- 有序链表的用途
有序链表可以用于实现优先级队列
有序链表可以用于数组的排序: 以插入排序为例,时间复杂度为O(N的平方).
- 代码示例
//链节点
public class Link {
private int data;
public Link next;
public Link(int data){
this.data = data;
}
public int getData(){
return this.data;
}
public void display(){
System.out.println("节点是"+data+",它的下一个节点是"+(null==next?"null":this.next.getData()));
}
}
//有序链表
public class SortedLinkList {
private Link first;
public SortedLinkList(){
this.first = null;
}
//插入时进行排序
public void insert(Link link){
Link pre = null;
Link cur = first;
while(cur!=null && link.getData() <= cur.getData()){
pre = cur;
cur = cur.next;
}
if(null == pre){ //如果cur没有移动
first = link;
}else{
pre.next = link;
}
link.next = cur;
System.out.println("插入节点:"+link.getData());
}
//删除一般只删除表头节点
public Link remove(){
Link temp = first;
if(null!=first){
first = first.next;
}
System.out.println("取出节点:"+(null==temp?"null":temp.getData()));
return temp;
}
public static void main(String[] args) throws Exception{
SortedLinkList list = new SortedLinkList();
list.insert(new Link(20));
list.insert(new Link(70));
list.insert(new Link(60));
list.remove();
list.remove();
list.remove();
}
}
输出:
插入节点:20
插入节点:70
插入节点:60
取出节点:70
取出节点:60
取出节点:20
4.双向链表
双向链表节点中有两个引用域,分别指向上一个节点和下一个节点,双向链表也可以是双端链表.
如图所示:
- 双向链表的应用
如文本编辑器中,光标不仅可以向前移动还可以向后移动.
- 代码示例
//链表
public class Link {
private int data;
public Link next;
public Link pre;
public Link(int data){
this.data = data;
}
public int getData(){
return this.data;
}
}
5.迭代器
将集合的和遍历相关操作委托给迭代器,通过迭代器中指针的移动进行相关操作.
- 代码示例
public class Link {
private int data;
public Link next;
public Link(int data){
this.data = data;
}
public void display(){
System.out.print(data+">");
}
}
public class LinkList {
private Link first;
public LinkList(){
first = null;
}
//获取第一个节点
public Link getFirst(){
return first;
}
//设置第一个节点
public void setFirst(Link f){
first = f;
}
//判空
public boolean isEmpty(){
return null == first;
}
//获取迭代器
public ListIterator getIterator(){
return new ListIterator(this);
}
//展示list
public void displayList(){
Link cur = first;
while(null != cur){
cur.display();
cur = cur.next;
}
System.out.println();
}
}
//迭代器的主要作用是将集合的一些遍历操作委托给迭代器
public class ListIterator {
private Link cur;
private Link pre;
private LinkList list;
public ListIterator(LinkList list){
this.list = list;
reset();
}
//重置迭代器
public void reset(){
cur = list.getFirst();
pre = null;
}
//判断是否在末尾
public boolean atEnd(){
return null == cur.next;
}
//指针移动到下一个
public void goNext(){
pre = cur;
cur = cur.next;
}
//获取当前指针
public Link getCur(){
return cur;
}
//在当前指针后插入
public void insertAfterCur(Link newLink){
//如果list为空
if(list.isEmpty()){
list.setFirst(newLink);
cur = newLink;
}else{
newLink.next = cur.next;
cur.next = newLink;
goNext();
}
}
//在当前指针前插入
public void insertBeforeCur(Link newLink){
if(null == pre){ //指针在链头
pre.next = list.getFirst();
list.setFirst(newLink);
reset();
}else{
newLink.next = pre.next;
pre.next = newLink;
cur = newLink;
}
}
//获取当前指针
public Link deleteCur(){
Link temp = cur;
if(list.isEmpty()){
System.out.println("链表为空!!!");
return null;
}
if(null == pre){//指针在链头
list.setFirst(cur.next);
reset();
}else{
pre.next = cur.next;
if(atEnd()){ //指针在链尾,直接移到链头
reset();
}else{
cur = cur.next;
}
}
return temp;
}
public static void main(String[] args) {
LinkList list = new LinkList();
ListIterator iterator = list.getIterator();
iterator.insertAfterCur(new Link(10));
iterator.insertAfterCur(new Link(20));
iterator.insertBeforeCur(new Link(30));
iterator.insertBeforeCur(new Link(40));
list.displayList();
iterator.deleteCur();
list.displayList();
}
}
输出:
10>40>30>20>
10>30>20>
6.扩展-合并k个有序链表
/**
* 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
* 示例:
* 输入:
* [
* 1->4->5,
* 1->3->4,
* 2->6
* ]
* 输出: 1->1->2->3->4->4->5->6
*/
public class MergeKListsSolution {
//方法一：递归合并两个有序链表，k个采用两两合并的方法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//该递归的边界，为l1或l2有一个为空
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
if (lists.length == 1) {
return lists[0];
}
ListNode temp = lists[0];
for (int i = 1; i < lists.length; i++) {
temp = this.mergeTwoLists(temp, lists[i]);
}
return temp;
}
//方法二：先从多个链头找出最小值，递归
public ListNode mergeKLists2(ListNode[] lists) {
//先确定递归的收敛边界,lists中不为空的元素个数为0或1
ListNode min = null;
int index = -1;
for (int i = 0; i < lists.length; i++) {
if (lists[i] == null) {
continue;
}
if (min == null || lists[i].val < min.val) {
min = lists[i];
index = i;
}
}
if (index != -1) {
lists[index] = lists[index].next;
min.next = mergeKLists2(lists);
}
return min;
}
}