## 结构与算法(03)：单向链表和双向链表

2020-10-18 05:40发布

# 一、链表简介

## 2、基础特点

• 物理存储上是无序且不连续的；
• 链表是由多个节点以链式结构组成；
• 逻辑层面上看形成一个有序的链路结构；

# 二、单向链表

## 2、基础操作

• 修改当前末尾节点的next指针；
• 新添加的节点房子在链表末尾；

# 三、双向链表

## 2、基础操作

• 遍历找到链表的最后一个节点；
• 修改当前末尾节点的next指针；
• 新添加的节点房子在链表末尾；
• 添加最新尾节点的prev指针；

• 双向链表，基于要删除节点操作即可；
• 操作上图中要删除的Node2节点；
• Node2.prev.next = Node2.next;
• Node2.next.prev = Node2.prev;

## 3、源码分析

``````public class M01_Linked {
public static void main(String[] args) {
List<User> userList = new LinkedList<>() ;
User removeUser = new User(200,"Second") ;
// 添加元素
System.out.println("初始化："+userList);
// 修改元素
System.out.println("修改后："+userList);
// 删除元素
userList.remove(removeUser) ;
System.out.println("删除后："+userList);
}
}
class User {
private Integer userId ;
public User(Integer userId, String userName) {
this.userId = userId;
}
@Override
public String toString() {
return "User{" +
"userId=" + userId +
'}';
}
// 省略Get和Set方法
}
``````

``````private static class Node<E> {
E item;         // 数据
Node<E> next;   // 下个指针
Node<E> prev;   // 上个指针
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
``````

``````public class LinkedList {
transient Node<E> first;
transient Node<E> last;
// 处理首节点
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
}
// 处理尾节点
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
}
}
``````

``````public boolean add(E e) {
return true;
}
``````

``````public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return true;
}
}
}
return false;
}
``````

``````E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
return element;
}
``````

# 五、源代码地址

``````GitHub·地址