动态链表就是链式存储结构具体实现的核心思想
linkedSinglyList就是线性结构链式存储方式的具体实现，称为单链表
package 动态链表;
import 动态数组.ArrayList;
import 接口.List;
import java.util.Comparator;
import java.util.Iterator;
//单向链表
public class LinkedSinglyList<E> implements List<E> {
//定义一个结点，用内部类来实现
private class Node{
E data;//数据域，用来存储数据的
Node next;//指针域，用来存储下一个结点对象的地址
public Node(){
this(null,null);
}
public Node(E data){
this(data,null);
}
public Node(E data,Node next){
this.data=data;
this.next=next;
}
public String toString(){
return data.toString();//由data的类型指定toString的内容
}
}
//定义一个头指针，指向第一个头结点的对象
private Node head;
//定义一个尾指针
private Node tail;
//定义一个有效元素的个数,指向最后一个结点的对象
private int size;
public LinkedSinglyList(){
head=null;
tail=null;
size=0;
}
public LinkedSinglyList(E [] arr){
for(E e:arr){
add(e);
}
}
@Override
public void add(E element) {
add(size,element);//注意这里的角标都是虚拟的，链表是不存在角标的
}
@Override
public void add(int index, E element) {
if(index<0||index>size){
throw new ArrayIndexOutOfBoundsException("角标不存在");
}
//创建一个新结点
Node node =new Node(element);
//1,链表为空
if(isEmpty()){
head=node;
tail=node;
// size++;
}
//2,表头添加
else if(index==0){
//在表头添加
node.next=head;
head=node;
}
//3,在表尾添加
else if(index==size){
tail.next=node;//node.next只是一个形象化的代称而已
tail=node;
}
else{
//4,在表中间添加元素
Node p =head;
for(int i=0;i<index-1;i++){
p=p.next;
}
node.next =p.next;
p.next=node;
}
size++;
}
@Override
public void remove(E element) {
int index=indexOf(element);
if(index!=-1){
remove(index);
}
}
//删除链表指定角标处的元素
@Override
public E remove(int index) {
if(index<0||index>=size){
throw new ArrayIndexOutOfBoundsException("角标不存在");
}
E ret =null;
//1,当链表只剩一个元素
if(size==1){
ret =head.data;
head=null;
tail=null;
}
//2,如果是表头
else if(index==0){
Node del=head;
ret =del.data;//和head.data是同一个值
head =del.next;
del.next=null;
}
//3，删除表尾元素
else if(index==size-1){
Node p=head;
while(p.next!=tail){
p=p.next;
}
ret =tail.data;
p.next=null;
tail=p;
}
else{
//4,删除中间某一个元素
Node p=head;
for(int i=0;i<index-1;i++){
p=p.next;
}
//要删除的结点
Node del =p.next;
ret =del.data;
p.next=del.next;
del.next=null;
}
size--;
return ret;
}
//获取链表中指定角标的元素
@Override
public E get(int index) {
if(index<0||index>=size){
throw new ArrayIndexOutOfBoundsException("角标不存在");
}
//1,获取头
if(index==0){
return head.data;
}
else if(index==size-1){
//获取尾部
return tail.data;
}
else{
//获取中间
Node p=head;
for(int i=0;i<index;i++){//直接获取到本身
p=p.next;
}
return p.data;
}
//return null;
}
//修改链表中指定角标的元素
@Override
public E set(int index, E element) {
if(index<0||index>=size){
throw new ArrayIndexOutOfBoundsException("角标不存在");
}
E ret =null;
//1，修改头
if(index==0){
ret =head.data;
head.data =element;
}
else if(index==size-1){
ret = tail.data;
tail.data= element;
}
else{
//3，修改中间
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
ret =p.data;
p.data=element;
}
return ret;
}
@Override
public int size() {
return size;
}
//查找元素在链表中第一次出现的角标
@Override
public int indexOf(E element) {
Node p=head;
int index=0;
while(!p.data.equals(element)){
p=p.next;index++;
if(p==null){
return -1;
}
}
return index;
}
//在链表中判断是否包含元素element
@Override
public boolean contains(E element) {
return indexOf(element)!=-1;
}
@Override
public boolean isEmpty() {
return size==0&&head==null&&tail==null;
}
@Override
public void clear() {
head =null;
tail =null;
size=0;
}
@Override
public void sort(Comparator<E> c) {
if(c==null){
throw new IllegalArgumentException("比较器c不能为空");
}
// int j;
// E e =null;
// for(int i=1;i<size;i++){
// e =get(i);
// for(j=i;j>0&&c.compare(get(j-1),e)>0;j--){
// set(j,get(j-1));
// }
// set(j,e);
// }
//改进
if(size==0||size==1){
return;
}
Node A =head;
Node B=A.next;
while (true){
while (true){
if(c.compare(A.data,B.data)>0){
swap(A,B);
}
if(B==tail) {
break;
}
B =B.next;
}
if(A.next==tail){
break;
}
A=A.next;
B=A.next;
}
}
private void swap(Node a, Node b) {
E temp=a.data;
a.data=b.data;
b.data=temp;
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
//先判断条件是否满足
if(fromIndex<0){
throw new IllegalArgumentException("fromIndex不能小于0");
}
if(toIndex>=size){
throw new IllegalArgumentException("toIndex不能>=size");
}
if(toIndex<fromIndex){
throw new IllegalArgumentException("toIndex不能大于fromIndex");
}
//创建一个线性表
LinkedSinglyList<E> subList =new LinkedSinglyList<>();
// for(int i=fromIndex;i<=toIndex;i++){
// //默认在表尾添加
// subList.add(get(i));
// }
//改进
Node A =head;
for(int i=0;i<fromIndex;i++){
A=A.next;
}
Node B =head;
for(int i=0;i<toIndex;i++){
B=B.next;
}
Node p=A;
while (true){
subList.add(p.data);
if(p==B){
break;
}
p=p.next;
}
return subList;
}
public String toString(){
StringBuilder sb =new StringBuilder(String.format("LinkedSinglyList:%d[",size));
if(isEmpty()){
sb.append("]");
}
else{
Node p=head;
while (true){
sb.append(p.data);
if(p==tail){
sb.append("]");
break;
}
sb.append(",");
p=p.next;
}
}
return sb.toString();
}
@Override
public Iterator<E> iterator() {
return new LinkedSinglyIterator();
}
class LinkedSinglyIterator implements Iterator<E>{
private Node cur =head;
@Override
public boolean hasNext() {
return cur!=null;
}
@Override
public E next() {
E ret =cur.data;
cur=cur.next;
return ret;
}
}
}