单向链表
这个是数据结构中最为基础的两大结构之一,后面的栈和队列都会用到单向链表作为底层,所以学好了单向链表你就成功了一大半了!
1,链表都必须的东西----节点对象node
public class Node {
private Object data; //存放数据
private Node next; //存放指针
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
public Node(Object data) {
this.data = data;
this.next=null;
}
public Node() {
this.data=null;
this.next=null;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
这个节点对象很容易理解就是两个属性一个用来存放数据data,另一个存放指针next指向下一个对象数据
2,创建接口用来定义方法
public interface MyList {
public void clear(); //让链表为空
public boolean isEmpty(); //判断链表是否为空
public int length(); //返回链表中的元素长度
public Object get(int i); //获得指定索引上的元素
public void insert(int i,Object x)throws Exception; //在指定索引位置上插入指定数据
public void add(Object x) throws Exception; //插入指定数据
public void remove(int i)throws Exception; //删除指定索引上的元素
public void delete(Object x)throws Exception; //删除指定元素
public void printList() ; //遍历链表中的所有元素
public int getData(Object x); //获得指定元素的索引
}
你也可以不写接口但是写接口会显得更专业一点
3,编写一个实现类
public class MyLinkedList implements MyList{
private Node header;//头节点
private int size;//元素个数
public MyLinkedList() {
this.header=new Node(null);
this.size=0;
}
}
这里的构造方法是为了初始化的作用 , 创建一个新的node对象不给他赋值用来作为一个头结点 , 这个头节点不用存储数据 . 然后初始化size的个数为0.*
这个就是链表的基本结构
4,实现接口中的方法
1,clear,isEmpty,length三个简单一点的方法
@Override
public void clear() {
header.setNext(null);
}
@Override
public boolean isEmpty() {
return this.size==0;
}
@Override
public int length() {
return this.size;
}
clear方法 : 直接让头节点的下一位指针指向一个空;
isEmpty方法 : 直接返回size属性是否为0用来判断该链表是否为空
length方法 : 直接返回size的值就为链表的有效长度
2,add,insert两个添加方法
@Override
public void insert(int i, Object x) throws Exception {
if(i<0||i>=size) {
throw new Exception("索引不合法");
}
Node newNode=new Node(x);
Node temp=header.getNext();
while(temp.getNext()!=null && i>=0) {
temp=temp.getNext();
i--;
}
newNode.setNext(temp.getNext());
temp.setNext(newNode);
size++;
}
@Override
public void add(Object x) throws Exception {
Node newNode=new Node(x);
if(size==0) {
header.setNext(newNode);
}else{
Node temp=header.getNext();
while(temp.getNext()!=null) {
temp=temp.getNext();
}
temp.setNext(newNode);
}
size++;
}
insert方法 :
1,判断索引的取值是否合法 如果索引小于0则不合法 , 如果索引大于size有效元素的个数则索引不合法
2,创建一个node对象newNode并且用构造方法传入指定元素x.
3,创建一个node对象temp用来存储与header节点连接的第一个数据
4,while循环将指定索引上面的数据通过循环存入temp中
5,将指定索引上数据temp的下一位数据拼在newNode的屁股后面
6,然后再把newNode拼接在temp的后面这样链表就连接起来了
7,size的个数加一
add方法 :
1,创建一个node对象newNode并且用构造方法传入指定元素x.
2,判断size是否为0 , 如果是则证明这个链表为空,就直接把元素插在header头节点的后面第一个
3,创建一个node对象temp用来存储与header节点连接的第一个数据
4,while循环将指定索引上面的数据通过循环存入temp中
5,一直遍历到最后一个元素然后存在temp中,然后将我们指定的newNode元素接在temp的后面
6,size的个数加一
add和insert方法基本思路是一样的 , 如果指定了索引就通过循环找出索引位置的数据在他后面添加新数据 , 然后把指定位置数据的后一个数据跟newNode连接 . 如果没有指定索引那就简单了直接循环到最后一个元素然后接在后面
3,remove和delete两个删除方法
@Override
public void remove(int i) throws Exception {
if(size==0) {
System.out.println("没有元素");
}else {
int k=0;
Node temp=header.getNext();
Node prTemp=header;
while(temp.getNext()!=null) {
if(k==i) {
prTemp.setNext(temp.getNext());
}
prTemp=temp;
k++;
temp=temp.getNext();
}
size--;
}
}
@Override
public void delete(Object x) throws Exception {
if(size==0) {
System.out.println("满了");
}else {
Node temp=header.getNext();
Node prTemp=header;
while(temp.getNext()!=null) {
if(temp.getData()==x) {
prTemp.setNext(temp.getNext());
}
prTemp=temp;
temp=temp.getNext();
}
size--;
}
}
remove方法 :
1,首先判断链表的有效元素个数size的大小 , 如果size==0就说明这个链表是空的没有元素 , 直接返回无元素或者抛出异常
2,创建一个int类型的k作为计数用
3,如果有元素那么创建temp存放header头节点的下一个元素
4,创建一个新的node节点prtemp对象存入header头节点
5,通过循环把指定索引前面的第一个元素存入prtemp中
6,通过while循环获取到指定索引位置的数据存入temp中
7,如果k==i那么此时temp存入的是指定索引的数据 , 而prtemp中存入的是指定索引数据的前一个数据 , 此时只需要把prtemp的next指针指向temp的下一位这样就可以直接将索引位置的数据删除
8,有效个数size–;
delete方法 :
1,首先判断链表的有效元素个数size的大小 , 如果size==0就说明这个链表是空的没有元素 , 直接返回无元素或者抛出异常
2,如果有元素那么创建temp存放header头节点的下一个元素
3,创建一个新的node节点prtemp对象存入header头节点
4,通过循环把指定索引前面的第一个元素存入prtemp中
5,通过while循环获取到指定索引位置的数据存入temp中
6,如果temp中存入的数据temp.getdata==x那么此时temp存入的是指定索引的数据 , 而prtemp中存入的是指定索引数据的前一个数据 , 此时只需要把prtemp的next指针指向temp的下一位这样就可以直接将索引位置的数据删除
7,有效个数size–;
**remove和delete方法都有异曲同工之妙创建了pretemp和temp对象用来存储指定元素前面一个元素和指定元素 , 删除操作也很简单就是通过让指定元素前后指针绕开他与后面连接 , 就会形成没有指针指向指定元素从而达到删除效果 **
get方法 :
@Override
public Object get(int i) {
if(size==0) {
System.out.println("没元素");
}else {
Node temp=header.getNext();
while(temp.getNext()!=null && i>=0) {
temp=temp.getNext();
i--;
}
return temp.getData();
}
return null;
}
1,首先判断链表的有效元素个数size的大小 , 如果size==0就说明这个链表是空的没有元素 , 直接返回无元素或者抛出异常
2,如果有元素那么创建temp存放header头节点的下一个元素
3,通过while循环获取到指定索引位置的数据存入temp中
4,返回temp中的data就是指定索引上的元素
5,如果不满足就返回null
getData方法 :
@Override
public int getData(Object x) {
if(size==0) {
System.out.println("无元素");
}else {
int i=0;
Node temp=header.getNext();
while(temp.getNext()!=null) {
if(temp.getData()==x) {
return i;
}
i++;
temp=temp.getNext();
}
}
return -1;
}
1,首先判断链表的有效元素个数size的大小 , 如果size==0就说明这个链表是空的没有元素 , 直接返回无元素或者抛出异常
2,设置int类型的i作为计数
3,如果有元素那么创建temp存放header头节点的下一个元素
4,通过循环获得data==x的数据存入temp中
5,i的值为循环的次数同时也是索引的值
get和getData方法都很像通过循环获得了指定位置的数据存入temp中然后 , 用int类型的变量进行计数获得索引.
printList方法
@Override
public void printList() {
if(size==0) {
System.out.println("无元素");
}else {
Node temp=header.getNext();
while(temp.getNext()!=null) {
System.out.print(temp.getData()+" , ");
temp=temp.getNext();
}
System.out.println(temp.getData());
}
}
1,首先判断链表的有效元素个数size的大小 , 如果size==0就说明这个链表是空的没有元素 , 直接返回无元素或者抛出异常
2,如果有元素那么创建temp存放header头节点的下一个元素
3,每一次都输出temp中data的值
最后发一下整体代码
public class MyLinkedList implements MyList{
private Node header;//头节点
private int size;//元素个数
public MyLinkedList() {
this.header=new Node(null);
this.size=0;
}
@Override
public void clear() {
header.setNext(null);
}
@Override
public boolean isEmpty() {
return this.size==0;
}
@Override
public int length() {
return this.size;
}
@Override
public Object get(int i) {
if(size==0) {
System.out.println("没元素");
}else {
Node temp=header.getNext();
while(temp.getNext()!=null && i>=0) {
temp=temp.getNext();
i--;
}
return temp.getData();
}
return null;
}
@Override
public void insert(int i, Object x) throws Exception {
if(i<0||i>=size) {
throw new Exception("索引不合法");
}
Node newNode=new Node(x);
Node temp=header.getNext();
while(temp.getNext()!=null && i>=0) {
temp=temp.getNext();
i--;
}
newNode.setNext(temp.getNext());
temp.setNext(newNode);
size++;
}
@Override
public void add(Object x) throws Exception {
Node newNode=new Node(x);
if(size==0) {
header.setNext(newNode);
}else{
Node temp=header.getNext();
while(temp.getNext()!=null) {
temp=temp.getNext();
}
temp.setNext(newNode);
}
size++;
}
@Override
public void remove(int i) throws Exception {
if(size==0) {
System.out.println("满了");
}else {
int k=0;
Node temp=header.getNext();
Node prTemp=header;
while(temp.getNext()!=null) {
if(k==i) {
prTemp.setNext(temp.getNext());
}
prTemp=temp;
k++;
temp=temp.getNext();
}
size--;
}
}
@Override
public void delete(Object x) throws Exception {
if(size==0) {
System.out.println("无元素");
}else {
Node temp=header.getNext();
Node prTemp=header;
while(temp.getNext()!=null) {
if(temp.getData()==x) {
prTemp.setNext(temp.getNext());
}
prTemp=temp;
temp=temp.getNext();
}
size--;
}
}
@Override
public void printList() {
if(size==0) {
System.out.println("无元素");
}else {
Node temp=header.getNext();
while(temp.getNext()!=null) {
System.out.print(temp.getData()+" , ");
temp=temp.getNext();
}
System.out.println(temp.getData());
}
}
@Override
public int getData(Object x) {
if(size==0) {
System.out.println("无元素");
}else {
int i=0;
Node temp=header.getNext();
while(temp.getNext()!=null) {
if(temp.getData()==x) {
return i;
}
i++;
temp=temp.getNext();
}
}
return -1;
}
}
**小结**
单链列表是数据结构中最为基础的结构我们必须要牢记并且熟练掌握 , 本身不是很难我们需要理解的是temp通过循环获得指定元素 , 还有就是链表的删除和插入的原理 . 一定要熟记
