上一篇发表的数组的基本操作,但是数组有优势也有劣势:
·具体的优势是:拥有高效的随机访问能力
·劣势是:由于排列紧密相连，插入和删除元素都会导致大量元素被迫移动，影响效率。
接下来要阐述的数据结构是链表:
·先看看单向链表的结构:
单向链表的每一个节点又包含两个部分，一部分是存放数据的变量data，另一部分是指向下一节点的指针next。
private static class Node{
int data;
Node next;
}
再看看双向链表:
·如果说数组在内存中的存储方式是顺序存储，那链表在内存中的存储方式是随机存储，
链表的每一个节点分布在不同的位置上，依靠next指针练习起来。
进入正题:链表的基本操作！
1.查找节点:
查找元素时，链表只能从头节点开始向后一个一个节点逐一查找
第一步:将查找的指针定位到头节点;
第二步:根据头节点的next指针,定位到第2个节点;
第三步:以此类推。
public Node get(int index) throws Exception{
if(index<0||index>=size){
throw new IndexOutOfBoundsException("访问越界!!!");
}
//将查找的指针定位到头节点
Node temp=head;
for(int i=0;i<index;i++){
temp=temp.next;
}
return temp;
}
2.更新节点:
链表的更新过程与数组类似，直接将旧数据替换成新数据即可。
public void updateNode(int data,int index) throws Exception{
if(index<0||index>size){
throw new IndexOutOfBoundsException("访问越界!!!");
}
Node temp=head;
for(int i=0;i<index;i++){
temp=temp.next;
}
temp.data=data;
}
3.插入节点:
与数组类似,链表插入节点时，同样分为三种情况:
尾部插入:
把最后一个节点的next指针指向新插入的节点即可。
头部插入:
大致分为两步
第一步:将新节点的next指针指向原先的头节点;
第二步:将新节点变成链表的头节点。
中间插入:
分为两步
第一步:新节点的next指针，指向插入位置的节点;
第二部:插入位置前置节点的next指针，指向新节点。
public void insert(int data,int index) throws Exception{
//判断是否访问越界
if(index<0||index>size){
throw new IndexOutOfBoundsException("访问链表越界!!!");
}
//创建一个节点
Node insertdNode=new Node(data);
if(size==0){
//空链表
head=insertdNode;
last=insertdNode;
}else if(index==0){
//插入头部
insertdNode.next=head;
head=insertdNode;
}else if(index==size){
//插入尾部
last.next=insertdNode;
last=insertdNode;
}else{
//插入中间
Node preNode=get(index-1);//插入位置的前置节点
insertdNode.next=preNode.next;
preNode.next=insertdNode;
}
size++;
}
4.删除节点:
分为三种情况
-
尾部删除: -
将倒数第二个节点的next指针指向空即可。 -
头部删除: -
将链表的头节点设为原先头节点的next指针即可。 -
中间删除: -
将要删除的节点的前置节点的next指针指向要删除节点的下一个节点即可。
public Node remove(int index) throws Exception{
//判断是否访问越界
if(index<0||index>=size){
throw new IndexOutOfBoundsException("访问越界!!!");
}
//初始化删除节点
Node removedNode=null;
if(index==0){
//删除头节点
removedNode=head;
head=head.next;
}else if(index==size){
//删除尾节点
Node preNode=get(index-1);
removedNode=preNode.next;
preNode.next=null;
last=preNode;
}else{
//删除中间节点
Node preNode=get(index-1);//要删除节点的前置节点
removedNode=preNode.next;
preNode.next=preNode.next.next;
}
size--;
return removedNode;
}
5.链表基本操作的完整代码:
点击查看代码
package LiknList;
public class MyLinkList {
//链表节点
private static class Node{
int data;
Node next;
Node(int data){
this.data=data;
}
}
//头节点指针
private Node head;
//尾部节点
private Node last;
//链表实际长度
private int size;
//链表插入元素(int data:要插入的元素,int index:要插入的位置)
public void insert(int data,int index) throws Exception{
//判断是否访问越界
if(index<0||index>size){
throw new IndexOutOfBoundsException("访问链表越界!!!");
}
//创建一个节点
Node insertdNode=new Node(data);
if(size==0){
//空链表
head=insertdNode;
last=insertdNode;
}else if(index==0){
//插入头部
insertdNode.next=head;
head=insertdNode;
}else if(index==size){
//插入尾部
last.next=insertdNode;
last=insertdNode;
}else{
//插入中间
Node preNode=get(index-1);//插入位置的前置节点
insertdNode.next=preNode.next;
preNode.next=insertdNode;
}
size++;
}
//链表删除元素(index:删除的位置)
public Node remove(int index) throws Exception{
//判断是否访问越界
if(index<0||index>=size){
throw new IndexOutOfBoundsException("访问越界!!!");
}
//初始化删除节点
Node removedNode=null;
if(index==0){
//删除头节点
removedNode=head;
head=head.next;
}else if(index==size){
//删除尾节点
Node preNode=get(index-1);
removedNode=preNode.next;
preNode.next=null;
last=preNode;
}else{
//删除中间节点
Node preNode=get(index-1);//要删除节点的前置节点
removedNode=preNode.next;
preNode.next=preNode.next.next;
}
size--;
return removedNode;
}
//链表查找元素(index:查找的位置)
public Node get(int index) throws Exception{
if(index<0||index>=size){
throw new IndexOutOfBoundsException("访问越界!!!");
}
//将查找的指针定位到头节点
Node temp=head;
for(int i=0;i<index;i++){
temp=temp.next;
}
return temp;
}
//更新节点(data:更新的数据,index:更新的位置)
public void updateNode(int data,int index) throws Exception{
if(index<0||index>size){
throw new IndexOutOfBoundsException("访问越界!!!");
}
Node temp=head;
for(int i=0;i<index;i++){
temp=temp.next;
}
temp.data=data;
}
//输出链表
public void output(){
Node temp=head;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public static void main(String[] args) throws Exception {
MyLinkList myLinkList=new MyLinkList();
myLinkList.insert(3,0);
myLinkList.insert(7,1);
myLinkList.insert(9,2);
myLinkList.insert(5,3);
myLinkList.insert(6,1);
myLinkList.remove(0);
myLinkList.updateNode(4,1);
myLinkList.output();
}
}
6.数组和链表的好与坏:
数组:查找和更新都是O(1),插入和删除是O(n);
链表:查找是O(n),其余都是O(1)。