一：单向链表
?链表是一个一个元素的添加的
?
每一个节点都是用到时 才会进行分配内存空间
?由于动态数组和链表中? 接口方法是相同的但是实现的代码是不一样的
因此我们定义一个接口List
实现这个接口的每一个类都应该实现这个接口中的所有方法
?插播一条Java语法的问题：
我们的动态数组ArrayList和链表LinkedList都是实现于List的
因此我们可以用类似于多态的形式进行new
?接口设计：
?
clear：
next不需要设置为null
因为当size==0时? 第一个节点消失死亡 跟着的后面节点一个一个也跟着死亡消失?
add:
步骤：找到要添加到位置的前一个元素
让添加的元素的next指向1处的22
让0处的next指向添加元素的44?
1. 找到对应索引下标的节点node
?2.获取某个节点处的元素值
?3.add
先找到要添加位置的前一个位置
之后再进行new出来一个新的节点
但是如果增加到0下标处时
我们需要改正? 改正如下：
我们需要让头节点的指向也就是这里的first指向重新定义
?
如果增加到最后一个位置时? 但是这种情况可以被第二种添加方式所包含
?
?删除：
?获取前面一个元素??
让前面一个next的指向? 指向下一个位置
?这里的first也就是链表头节点的first
?练习题1：
?
思路：
1.首先用要被删除元素的元素的值进行覆盖 node.val=node.next.val;
2.再用要被删除元素的前一个结点的next指向node.next.next
node.next=node.next.next;
?
练习题2：
反转：
方法一：递归方法
举个例子：
当我们函数传参传递的是4时 那么反转之后的链表形式如图?：
?
?
?
?
?习题3：
package 链表动态数组.链表.单链表;
import 链表动态数组.链表.双向链表.双向链表;
public class LinkedList<E> extends 双向链表<E>{
/**
* 清除所有元素
*/
public void clear(){
size=0;
first=null;
}
/**
* 元素的数量
*/
public int size() {
return size;
}
/**
* 判断是否为空
*/
public boolean isEmpty(){
return size==0;
}
/**
* 判断是否包含某个元素
*/
public boolean contains(E elements){
双向链表.Node node=first;
for (int i = 0; i < size; i++) {
if(node.element==elements){
return true;
}
node=node.next;
}
return false;
}
/**
* 添加元素到尾部
*/
public void add(int index,E element) {
if(index==0){
first=new 双向链表.Node<>(element,first);
} else {
双向链表.Node<E> prev=node(index-1);
prev.next=new 双向链表.Node<>(element,prev.next);
}
size++;
}
/**
*找到某一位置的节点并且返回
*/
private 双向链表.Node<E> node(int index){
双向链表.Node<E> node=first;
for (int i = 0; i <index; i++) {
node=node.next;
}
return node;
}
/**
* 获取index位置的元素
*/
public E get(int index) {
return node(index).element;
}
/**
* 设置index位置的元素
*/
public E set(int index,E element){
双向链表.Node<E> node=node(index);
E old=node.element;
node.element=element;
return old;//返回原来的元素值
}
/* *//**
* 在index插入一个元素
*//*
public void add(int index,E elememt) {
}*/
/**
* 删除index位置的元素
*/
public E remove(int index){
双向链表.Node<E> node=first;
if(index==0){
first=first.next;
} else {
双向链表.Node<E> prev=node(index-1);//找到前驱
node=prev.next;//对node重新赋值哦
prev.next=node.next;//进行删除
}
size--;
return node.element;//把这个被删除的节点的元素值进行返回
}
/**
* 查看元素的索引
*/
public int indexOf(E element){
if(element==null){
双向链表.Node<E> node=first;
for (int i = 0; i <size; i++) {
if(node.element==null){
return i;
}
node= ((Node<E>) node).next;
}
} else {
双向链表.Node<E> node=first;
for (int i = 0; i <size; i++) {
if(node.element.equals(element)){
return i;
}
node=node.next;
}
}
return ELEMENT_NOT_FOUND;
}
}?注意：
环形链表用快慢指针? 快慢指针初始指向位置是不同的
动态数组缩容操作：
?缩容和扩容差不多思想：把原来的元素移到新搞出来的数组内存
?二：双向链表
?找到对应index下标的节点node
因为这个节点node具有双指向性
next和prev指向 因此利用对称来找出对应索引处的节点
这样分一半一半的找
提高了效率
?
?clear:
当我们把LinkedList对象的两条线去掉以后
整个节点数组都会死掉
虽然说仍然有引用互相进行指向
但这些节点已经丧失了gc root对象的指向
JVM宣布他们这些节点全部死掉
那么作用之后只剩下：
?
?双向链表add：
first只关注第一个节点元素
last只关注最后一个节点元素?
?
?但如果最开始什么都没有：
last==null
?只有一个
/**
* 在index插入一个元素
*/
public void addindex(int index,E elememt) {
if (index < 0 || index > size) {
return;
}
if (index == size) {
Node oldlast=last;
Node leo=new Node(element,oldlast,null);
last=leo;
if(oldlast==null){//当只有一个元素的时候first last都指向这个节点
last=leo;
first=leo;
} else {
oldlast.next=last;
}
} else {
Node next = node(index);//找到要添加位置的节点
Node prev = next.prev;//要添加的节点的上一个
Node node = new Node(element, prev, next);
next.prev = node;
if (next.prev == null) {//index==0
first = node;
} else {
prev.next = node;
}
}?删除：
/**
* 删除index位置的元素
*/
public void remove(int index){
Node<E> node=node(index);
Node<E> prev=node.prev;//这里的prev next就相当于一个节点了吧
Node<E> next=node.next;
if(prev==null){
first=next;
} else {
prev.next=next;
}
if(next==null){
last=prev;
} else {
next.prev=prev;
}
}
双向链表总代码：
package 链表动态数组.链表.双向链表;
import 链表动态数组.链表.单链表.leo;
public class 双向链表<E> extends leo<E> {
//元素的数量
protected int size;
protected static final int ELEMENT_NOT_FOUND=-1;
protected Node<E> first;
private Node<E> last;
/**
*内部类定义一个Node类
*/
public static class Node<E>{
public E element;
Node<E> prev;
public Node<E> next;
public Node(E element, Node<E> prev, Node<E> next) {
this.element = element;
this.prev = prev;
this.next = next;
}
}
/**
* 清除所有元素
*/
public void clear(){
size=0;
first=null;
last=null;
}
/**
* 元素的数量
*/
public int size() {
return size;
}
/**
* 判断是否为空
*/
public boolean isEmpty(){
return size==0;
}
/**
* 判断是否包含某个元素
*/
public boolean contains(E elements){
Node node=first;
for (int i = 0; i < size; i++) {
if(node.element==elements){
return true;
}
node=node.next;
}
return false;
}
/**
*找到某一位置的节点并且返回
* 双向链表利用对称性 大大提高了查找速率
*/
private Node<E> node(int index){
if(index<0||index>size){
return null;
}
//当在左半边的时候
if(index<(size>>1)){
Node<E> node=first;
for (int i = 0; i <index; i++) {
node=node.next;
}
return node;
} else { //当在右半边的时候
Node<E> node=last;
for (int i =size-1; i <index; i++) {
node=node.prev;
}
return node;
}
}
/**
* 获取index位置的元素
*/
public E get(int index) {
return node(index).element;
}
/**
* 设置index位置的元素
*/
public E set(int index,E element){
Node<E> node=node(index);
E old=node.element;
node.element=element;
return old;//返回原来的元素值
}
/**
* 在index插入一个元素
*/
public void addindex(int index,E elememt) {
if (index < 0 || index > size) {
return;
}
if (index == size) {
Node oldlast=last;
Node leo=new Node(element,oldlast,null);
last=leo;
if(oldlast==null){//当只有一个元素的时候first last都指向这个节点
last=leo;
first=leo;
} else {
oldlast.next=last;
}
} else {
Node next = node(index);//找到要添加位置的节点
Node prev = next.prev;//要添加的节点的上一个
Node node = new Node(element, prev, next);
next.prev = node;
if (next.prev == null) {//index==0
first = node;
} else {
prev.next = node;
}
}
}
/**
* 删除index位置的元素
*/
public void remove(int index){
Node<E> node=node(index);
Node<E> prev=node.prev;
Node<E> next=node.next;
if(prev==null){
first=node;
} else {
prev.next=next;
}
if(next==null){
last=node;
} else {
next.prev=prev;
}
}
/**
* 查看元素的索引
*/
public int indexOf(E element){
if(element==null){
Node<E> node=first;
for (int i = 0; i <size; i++) {
if(node.element==null){
return i;
}
node=node.next;
}
} else {
Node<E> node=first;
for (int i = 0; i <size; i++) {
if(node.element.equals(element)){
return i;
}
node=node.next;
}
}
return ELEMENT_NOT_FOUND;
}
}
?单向循环链表：这是单链表
?当什么都没有 第一次添加节点的时候
?
?删除：
?特殊情况：只有一个节点·
package 链表动态数组.链表.单链表;
//循环链表与单链表的不同之处就在于add和remove
public class 单向循环链表<E> extends 单链表<E> {
@Override
public void addindex(int index, Object elememt) {
if(index<0||index>size){
return;
}
if(index==0){
Node node=new Node(elememt,first);
first=node;
//找到最后一个节点
Node last=node(index-1);
last.next=first;//循环链表的规定
} else {
Node<E> prev=node(index-1);
Node node=new Node(elememt,prev.next);
prev.next=node;
}
}
@Override
public E remove2(int index) {
if(index<0||index>size){
return null;
}
if(index==0){
if(size==1){
first=null;
} else {
Node<E> last=node(index-1);
Node<E> node=new Node<>(last.element,first.next);
last=node;
}
} else {
Node prev=node(index-1);
Node node=prev.next;
prev.next=node.next;
}
size--;
return null;
}
}
?双向循环链表：
?
?
?双向循环链表remove：
但是当链表原来只有一个节点的时候
上面代码应当修改：?
?
代码：
package 链表动态数组.链表.双向链表;
//循环链表与单链表的不同之处就在于add和remove
public class 双向循环链表<E> extends 双向链表<E> {
@Override
public void addindex(int index, Object elememt) {
if(index==size){
Node oldlast=last;
Node<E> node=new Node<E>((E)elememt,oldlast,first);
if(oldlast==null){
first=last;
first.prev=first;
first.next=first;
} else {
oldlast.next=node;
first.prev=node;
}
} else {
Node<E> next=node(index);
Node<E> prev=next.prev;
Node<E> node=new Node<E>((E) elememt,prev,next);
next.prev=node;
if(prev==null){//证明index==0
first=node;
} else {
prev.next=node;
}
}
size++;
}
@Override
public void remove(int index) {
if (index < 0 || index > size) {
return;
}
Node<E> node = first;
if (size == 1) {
first = null;
last = null;
} else {
node = node(index);
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
if(node==first){//index==0
first=next;
}
if(node==last){//index==size-1
last=prev;
}
}
}
}
?
?1.
2.
?
?
?3.封装一个remove方法直接删除传进来的节点
?4.运行测试：
?
?