1、链表初识（类型固定 容量固定）
·链表是线性表中常见的两种表现方式之一
·数据储存在节点（Node）中
·Node一般来说包括：元素、前驱、后继
·第一个节点的前驱是Null，最后一个节点的后继是Null
·真正的实现了动态，不需要考虑动态扩容问题
·查找困难
·引用（C中的指针） 非常考验对引用的理解
·几点可以使用内部类来实现
2、节点实现（内部类）
public class LinkedList<E> {
private class Node{
//元素
public E e;
//下一个节点
public Node next;
//指定元素与下一个节点的构造器
public Node(E e,Node next)
this.e=e;
this.next=next;
}
//指定元素，下一个节点设为null
public Node(E e) {
this(e,null);
}
//空构造器，元素与下一个节点均为null
public Node() {
this(null,null);
}
@Override
public String toString() {
return e.toString();
}
}
}3、基本成员
头结点
元素数量
public class LinkedList<E> {
//节点内部类
//1.链表是由节点串起来的2.下一节点应该作为引用
private class Node{
//元素
public E e;
//下一节点
public Node next;
//指定元素与下一节点的构造器
public Node(E e, Node next) {
this.e=e;
thsi.next=next;
}
//指定元素，下一节点设为null
public Node(E e) {
this(e,null);
//空构造器，元素与下一节点均为null
public Node() {
this(null,null)
}
@verride
public String toString() {
return e.toString();
}
}
//头结点
private Node head;
//元素数量
private int size;
//构造函数
public LinkedList() {
head=null;
size=0;
}
//获得元素数量
public int getSize() {
return size;
}
public boolean isEmpty() {
return size==0;
}
}4.添加操作
4.1在头部添加
public void addFirst(E e) {
//将传进来的元素 放进新生成的节点中
Node node =new Node(e);
//新生成的节点下一个指向现在的头节点
node.next=head;
//把新生成的节点作为头结点
head=node;
}4.2在任意位置添加
public void add(int index, E e) {
if(index<0||index>size) {
throw new IllegalArgumentException("索引位置不合法，添加失败");
}
if(index==0) {
addFirst(e);
} else{
Node prev=head;
//prev 节点向前移动
for(int i=0;i<index-1;i++) {
prev=prev.next;
}
Node node=new Node(e);
node.next=prev.next;
prev.next=node;
size++;
}
}
public void addLast(E e) {
add(size ,e);
}4.3 改进虚拟头结点
·由于在头部添加时，无前一个，所以产生了虚拟头结点
·虚拟头结点的元素是null，只想了实际的头一个节点
//头结点
private Ndoe visualHead
//元素数量
private int size;
//构造函数
public LinkedList() {
visualHead=new Node();
size=0;
}
//获得元素数量
public int getSize() {
return size;
}
//在头部添加元素
public void addFirst(E e) {
add(0,e);
}
public void add(int index,E e) {
if(index<0||index>size) {
throw new IllegalArgumentException("索引位置不合法，添加失败");
}
Node prev=prev.next;
}
Node node=new Node(e);
node.next=prev.next;
prev.next=node;
size++;
}
public void addLast(E e) {
add(size,e);
}
}5、查询操作
//根据缩印查找元素
public E get(int index) {
if(index<0||index>size) {
throw new IllegalArgumentException("索引位置不合法，查找失败");
}
Node current=visualHead.next;
for(int i=0;i<index;i++) {
current=current.next;
}
return current.e;
}
public E getFirst() {
return get(0);
}
public E getLast() {
return get(size-1);
}
//判断元素是否存在 根据元素查元素
public boolean contains(E e) {
Node current=visualHead.next;
while(current!=null) {
if(current.e.equals(e)) {
return true;
}
}
return false;
}6、更新操作
//修改链表中某处的元素
public void set(int index,E e) {
if(index<0||intdex>size) {
throw new IllegalArumentException("修改失败，参数不合法");
}
Node current=visualHead.next;
for(int i=0;i<index;i++) {
current=current.next;
}
current.e=e;
}7、遍历操作
@override
public String toString() {
StringBuilder res=new StringBuilder();
for (Node current = visualHead.next; current != null; current =current.next){
res.append(current+"->");
}
//追加一个null，表示链表结束
res,append("null");
reutn res.toString();
}8、删除操作
//根据索引删除元素
public E remove(int index) {
//参数合法性判断
if(index<0||index>=size) {
throw new IllegalArgumentException("删除失败，索引不合法");
}
//从虚拟头结点开始查找待删除结点的前一个
Node prev=visualHead;
//开始查找
for(int i=0;i<index;i++ {
prev=prev.next;
}
//待删除结点
Node retNode=prev.next;
//删除操作
//待删除结点的前一个指向待删除结点的下一个
prev.next=retNode.next;
retNode.next=null;
retutn retNode.e;
}删除首个元素,删除尾元素
//删除链表中的第一个元素
public E removeFirst() {
return remove(0);
}
//删除链表中的最后一个元素
public E romveLst() {
return remove(size-1);
}根据元素删除元素
public void removeElement(E e) {
//从虚拟头结点作为待删除结点的前一个
Node prev=visualHead;
//通过while循环找到待删除元素所在节点
while(prev.next!=null) {
//判断下一个的节点元素值与参数是否一致
if(prev.next.e.equals(e) {
//跳出循环，执行接下来的操作
breakl;
}
//prev向后传递
prev=prev.next;
}
Bode retNode=prev.next;
prev.next=retNode.next;
retNode.next=null;
size--;
}如有错误 感谢指正