数据结构——动态链表（GIF图解）

文章目录

• • 一、链表的定义
  • 二、头结点与头指针
  • 三、链表的实现
  • • • • 获取长度和判空
        • 插入元素 (头插)(尾插)(一般插入)
        • 获取链表中的元素
        • 修改元素
        • 判断包含和找元素
        • 删除元素(头删)(尾删)(一般删除)
        • 删除指定元素
        • 清空链表
        • 迭代器
        • 自定义格式打印链表中的数据

一、链表的定义

为了表示每个数据元素a1与其直接后继元素ai+1之间的逻辑关系，对数据元素a1来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域存储的信息称作链。这两部分信息组成数据元素ai的存储映像，称为结点。
n个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。（示意图如下）

二、头结点与头指针

头结点是指链表中第一个节点，有真实头结点和虚拟头结点之分。

三、链表的实现

链表实现的也是 List 接口，在前面的学习中已经写出了 List 接口，在这里就直接对接口的方法进行实现。
首先，写一个LinkedList 的一个构造函数和一个 Node 内部类(定义指针)。

//用动态链表实现的线性表 链表
public class LinkedList<E> implements List<E> {private Node head;  //链表的头指针(虚头结点)private Node rear;  //链表的尾指针private int size;   //链表的元素个数(结点个数)public LinkedList(){head=new Node();rear=head;}//定义一个指针类private class Node{E data;     //数据域Node next;  //指针域Node(){		//无参构造函数this(null,null);  //调用下面的有参构造函数}Node(E data,Node next){this.data=data;this.next=next;}@Overridepublic String toString() {return data.toString();}}
}

获取长度和判空

//获取长度@Overridepublic int getSize() {return size;}
//判空@Overridepublic boolean isEmpty() {return size==0&&head==rear;		//有效个数为0 且 头指针和尾指针在同一位置}

插入元素 (头插)(尾插)(一般插入)

头插只需要将原来头结点中的指针域给新插入元素的指针域，然后再将新结点的地址给原来头结点的指针域即可。（示意图如下）
尾插比较特殊，因为前的最后一个结点的指针域指向空，新元素的指针域也指向空，所以这里只需要将新结点的地址给尾结点的指针域 rear.next ，再将尾指针后移即可。（示意图如下）
一般插入，首先需要找到需要插入位置的前一个结点，在下面代码中给出了一个p指针来找前一个结点，所以只需要将p的指针域给新元素的指针域，然后将新元素的地址给 p 的指针域即可。（示意图如下）

• 以上三种插入元素的代码实现

@Overridepublic void add(int index, E e) {if(index<0||index>size){throw new IllegalArgumentException("角标越界");}Node n=new Node();n.data=e;if(isEmpty()){          //空表状态 特殊处理head.next=n;	rear=n;}else if(index==0){     //头插法n.next=head.next;head.next=n;}else if(index==size){  //尾插法rear.next=n;rear=n;}else{                  //中间插Node p=head;for(int i=0;i<index;i++){ //从头遍历找到需要插入元素的前一个位置p=p.next;}n.next=p.next;	//将p的指针域给所要插入元素n的指针域p.next=n;	//再将n的地址给p的指针域}size++;}
//头插@Overridepublic void addFirst(E e) {add(0,e);}
//尾插@Overridepublic void addLast(E e) {add(size,e);}

获取链表中的元素

@Overridepublic E get(int index) {if(isEmpty()){throw new IllegalArgumentException("空表");}if(index<0||index>=size){throw new IllegalArgumentException("角标越界");}if(index==0){	//角标为0 就是当前头结点的数据return head.next.data;}else if(index==size-1){	//角标为size-1 就是当前尾结点的数据return rear.data;}else{Node p=head;  //创建一个p指针从头开始找for(int i=0;i<=index;i++){p=p.next;}return p.data;}}//获取表头元素@Overridepublic E getFirst() {return get(0); 	//调用get函数}//获取表尾元素@Overridepublic E getLast() {return get(size-1);	//调用get函数}

修改元素

    @Overridepublic void set(int index, E e) {if(isEmpty()){throw new IllegalArgumentException("空表");}if(index<0||index>=size){throw new IllegalArgumentException("角标越界");}Node p=head;	//创建一个指针p从头开始找需要修改元素的位置for(int i=0;i<=index;i++){p=p.next;}p.data=e;  //更换数据}

判断包含和找元素

	//判断是否包含元素e@Overridepublic boolean contains(E e) {return find(e)!=-1;  	//调用下面find函数 如果能找到则一定包含}//找元素e@Overridepublic int find(E e) {Node p=head;	//创建指针p从头开始找元素efor(int i=0;i<size;i++){p=p.next;if(p.data.equals(e)){return i;	//找到则返回当前角标}}return -1;	//找不到返回-1}

删除元素(头删)(尾删)(一般删除)

头删，首先要新建一个变量 ret，将所要删除的数据存入 ret，然后删除该结点，然后把所要删除的结点的指针域给头结点的指针域即可。（示意图如下）
在头删的时候，也需要考虑链表中只剩一个有效结点的情况。（示意图如下）

尾删也需要先找到为节点的前一个元素，同样先把要删除的结点的数据存入 ret，然后再删除，这里只需要把删除之后的链表的尾结点的指针域指向空即可，再把尾指针前移。（示意图如下）

一般删除也是先找到需要删除原始的前一个位置，然后将要删除的结点的数据存入 ret，然后再删除，这里只需要把所要删除的结点的指针域给前一个结点的指针域即可。（示意图如下）

• 以上三种插入元素的代码实现

    @Overridepublic E remove(int index) {if(isEmpty()){throw new IllegalArgumentException("表空");}if(index<0||index>=size){throw new IllegalArgumentException("角标越界");}E ret=null;	//创建一个变量retif(size==1){   //只有一元素的时候ret=rear.data;  //将要删的结点的数据给变量rethead.next=null;	//将头结点的指针域指空rear=head;	//尾结点和头结点在同一位置}else if(index==0){   //因为本代码采用虚拟头结点，所以第一个元素角标为1   头删Node del=head.next;   //创建一个新指针del指向所要删除的结点ret=del.data;head.next=del.next;del.next=null;		// 释放空间 free(del)del=null;}else if(index==size-1){ 	//尾删Node p=head;  		//创建一个指针p从头开始找尾的前一个结点while(true){if(p.next!=rear){p=p.next;}else{break;}}ret=p.next.data;p.next=null;rear=p; 	//尾指针前移}else{		//一般删除Node p=head;  //创建一个指针p从头开始找所要删除的结点的前一个结点for(int i=0;i<index;i++){p=p.next;}Node del=p.next;  //创建一个指针del指向所要删除的结点ret=del.data;p.next=del.next;del.next=null;del=null;       // 释放空间 free(del)}size--;return ret;}//删头@Overridepublic E removeFirst() {return remove(0);}//删尾@Overridepublic E removeLast() {return remove(size-1);}

删除指定元素

   @Overridepublic void removeElement(E e) {int index=find(e);  //调用find函数先到元素eif(index!=-1){remove(index);  //调用remove函数删除}else{throw new IllegalArgumentException("找不到！");}}

清空链表

 @Overridepublic void clear() {head.next=null;rear=head;size=0;}

迭代器

@Overridepublic Iterator<E> iterator() {return new LinkedListIterator();}public class LinkedListIterator implements Iterator<E>{private Node p=head;@Overridepublic boolean hasNext() {return p.next!=null;}@Overridepublic E next() {p=p.next;return p.data;}}

自定义格式打印链表中的数据

   @Overridepublic String toString() {StringBuilder sb=new StringBuilder(); 	//创建一个对象sb.append("LinkedList : "+size+"\n");  	//调用append字符插入函数sb.append('[');if(isEmpty()){sb.append(']');}else{Node p=head;  //创建指针p从头开始遍历链表while(true){if(p.next!=rear){p=p.next;sb.append(p.data);sb.append(',');}else{sb.append(rear.data);sb.append(']');break;}}}return sb.toString();}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！