Java数据结构之链表详解

一、链表的介绍

什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表和数组的比较

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。

一句话就是链表因为内存是动态分配的所以添加和删除快,但是查询速度慢
数组因为有索引所以查找快,但是添加和删除慢,因为每次都要创建新的数组

二、单链表的实现

单链表在内存中的情况:

单链表的示意图:
每个节点包含data域和next域指向下一个节点

水浒里面的英雄好汉想必大家都听过,下面用一个带head节点的链表来实现对水浒英雄排名的增删改查操作来了解单链表的操作。

//英雄节点
public class HeroNode {
    public int no;//编号
    public String name;//名字
    public String nickname;//绰号
    HeroNode next;//下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickname() {
        return nickname;
    }

    public void setNickname(String nickname) {
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
//定义SingleLinkedList 管理好汉节点
class SingleLinkedList {
	//先初始化一个头节点, 头节点不动, 不存放具体的数据
	private HeroNode head = new HeroNode(0, "", "");

	//返回头节点
	public HeroNode getHead() {
		return head;
	}
	}

添加节点

不考虑好汉编号顺序
思路分析

1.找到当前链表的最后节点

2.将最后这个节点的next 指向 新的节点

public void add(HeroNode heroNode) {

		//因为head节点不能动,因此我们需要一个辅助节点遍历链表
		HeroNode temp = head;
		//遍历链表,找到最后
		while(true) {
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			//如果没有找到最后, 将将temp后移
			temp = temp.next;
		}
		//当退出while循环时,temp就指向了链表的最后
		//将最后这个节点的next 指向 新的节点
		temp.next = heroNode;
	}

第二种方式考虑好汉编号顺序,根据排名将好汉插入到指定位置(如果没有这个排名,则添加失败,并给出提示)

public void addByOrder(HeroNode heroNode) {
		//因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
		HeroNode temp = head;
		boolean flag = false; // flag标志添加的编号是否存在,默认为false
		while(true) {
			if(temp.next == null) {//说明temp已经在链表的最后
				break;
			}
			if(temp.next.no > heroNode.no) { //位置找到,就在temp的后面插入
				break;
			} else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在

				flag = true; //说明编号存在
				break;
			}
			temp = temp.next; //后移,遍历当前链表
		}
		//判断flag 的值
		if(flag) { //不能添加,说明编号存在
			System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
		} else {
			//插入到链表中, temp的后面
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

修改节点

根据 newHeroNode 的 no 来修改

public void update(HeroNode newHeroNode) {
		//判断是否空
		if(head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		//找到需要修改的节点, 根据no编号
		//定义一个辅助变量
		HeroNode temp = head.next;
		boolean flag = false; //表示是否找到该节点
		while(true) {
			if (temp == null) {
				break; //已经遍历完链表
			}
			if(temp.no == newHeroNode.no) {
				//找到
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//根据flag 判断是否找到要修改的节点
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else { //没有找到
			System.out.printf("没有找到 编号 %d 的节点,不能修改\n", newHeroNode.no);
		}
	}

删除节点

根据 要删除的 no 来删除

public void delete(int no) {
		HeroNode temp = head;
		boolean flag = false; // 标志是否找到待删除节点的
		while(true) {
			if(temp.next == null) { //已经到链表的最后
				break;
			}
			if(temp.next.no == no) {
				//找到的待删除节点的前一个节点temp
				flag = true;
				break;
			}
			temp = temp.next; //temp后移,遍历
		}
		//判断flag
		if(flag) { //找到
			//可以删除
			temp.next = temp.next.next;
		}else {
			System.out.printf("要删除的 %d 节点不存在\n", no);
		}
	}

查找节点

根据 输入的 no 来查找

public void search(int no) {
		HeroNode temp = head;
		boolean flag = false; // 标志是否找到节点
		while(true) {
			if(temp.next == null) { //已经到链表的最后
				break;
			}
			if(temp.no == no) {
				//找到了该节点
				flag = true;
				break;
			}
			temp = temp.next; //temp后移,遍历
		}
		//判断flag
		if(flag) {
		//找到了该节点
		System.out.printf("要查找的 %d 节点是\n", temp);
		}else {
			System.out.printf("要查找的 %d 节点不存在\n", no);
		}
	}

遍历链表

public void list() {
		//判断链表是否为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		//因为头节点,不能动,因此我们需要一个辅助变量来遍历
		HeroNode temp = head.next;
		while(true) {
			//判断是否到链表最后
			if(temp == null) {
				break;
			}
			//输出节点的信息
			System.out.println(temp);
			//将temp后移, 一定小心
			temp = temp.next;
		}
	}
}

测试:

public static void main(String[] args) {
		//先创建节点
		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero4);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);
		singleLinkedList.list();
		System.out.println("删除一个节点");
		singleLinkedList.del(3);
		singleLinkedList.update(new HeroNode(1,"宋江","义薄云天"));
		singleLinkedList.list();

HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
删除一个节点
HeroNode [no=1, name=宋江, nickname=义薄云天]
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]

三、双向链表的实现

双向链表的介绍

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。如下图所示:

双向链表的分析

单向链表查找的方向只有一个,而双向链表可以向前或向后查找,实现双向查找。
单向链表不能自我删除,而双向链表可以自我删除。
我们依旧通过水浒英雄的例子来实现双向链表的增删改查操作。

// 定义HeroNode2 , 每个HeroNode 对象就是一个节点
class HeroNode2 {
	public int no;
	public String name;
	public String nickname;
	public HeroNode2 next; // 指向下一个节点, 默认为null
	public HeroNode2 pre; // 指向前一个节点, 默认为null

	public HeroNode2(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}

}
// 创建一个双向链表的类
class DoubleLinkedList {

	// 先初始化一个头节点, 头节点不动, 不存放具体的数据
	private HeroNode2 head = new HeroNode2(0, "", "");

	// 返回头节点
	public HeroNode2 getHead() {
		return head;
	}
}

遍历链表

// 创建一个双向链表的类
class DoubleLinkedList {

	// 先初始化一个头节点, 头节点不动, 不存放具体的数据
	private HeroNode2 head = new HeroNode2(0, "", "");

	// 返回头节点
	public HeroNode2 getHead() {
		return head;
	}
}

添加节点

public void add(HeroNode2 heroNode) {

		// 因为head节点不能动,因此我们需要一个辅助遍历 temp
		HeroNode2 temp = head;
		// 遍历链表,找到最后
		while (true) {
			// 找到链表的最后
			if (temp.next == null) {//
				break;
			}
			// 如果没有找到最后, 将将temp后移
			temp = temp.next;
		}
		// 当退出while循环时,temp就指向了链表的最后
		// 形成一个双向链表
		temp.next = heroNode;
		heroNode.pre = temp;
	}

修改节点

public void update(HeroNode2 newHeroNode) {
		// 判断是否空
		if (head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		// 找到需要修改的节点, 根据no编号
		// 定义一个辅助变量
		HeroNode2 temp = head.next;
		boolean flag = false; // 表示是否找到该节点
		while (true) {
			if (temp == null) {
				break; // 已经遍历完链表
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// 根据flag 判断是否找到要修改的节点
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else { // 没有找到
			System.out.printf("没有找到 编号 %d 的节点,不能修改\n", newHeroNode.no);
		}
	}

删除节点

// 1 对于双向链表,我们可以直接找到要删除的这个节点
	// 2 找到后,自我删除即可
	public void del(int no) {

		// 判断当前链表是否为空
		if (head.next == null) {// 空链表
			System.out.println("链表为空,无法删除");
			return;
		}

		HeroNode2 temp = head.next; // 辅助变量(指针)
		boolean flag = false; // 标志是否找到待删除节点的
		while (true) {
			if (temp == null) { // 已经到链表的最后
				break;
			}
			if (temp.no == no) {
				// 找到的待删除节点的前一个节点temp
				flag = true;
				break;
			}
			temp = temp.next; // temp后移,遍历
		}
		// 判断flag
		if (flag) { // 找到
			// 可以删除
			// temp.next = temp.next.next;[单向链表]
			temp.pre.next = temp.next;
			// 这里我们的代码有问题?
			// 如果是最后一个节点,就不需要执行下面这句话,否则出现空指针
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.printf("要删除的 %d 节点不存在\n", no);
		}
	}

测试

public static void main(String[] args) {
        // 测试
        System.out.println("双向链表的测试");
        // 先创建节点
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
        // 创建一个双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);

        doubleLinkedList.list();

        // 修改
        HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况");
        doubleLinkedList.list();

        // 删除
        doubleLinkedList.del(3);
        System.out.println("删除后的链表情况~~");
        doubleLinkedList.list();
}

双向链表的测试
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
修改后的链表情况
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=公孙胜, nickname=入云龙]
删除后的链表情况~~
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=4, name=公孙胜, nickname=入云龙]

四、循环链表的实现

循环链表介绍

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

循环链表实现

public class LoopLinkedList {
     Node head;//头结点
     Node tail;//尾结点
     int size;//链表大小

    public LoopLinkedList() {
        head=tail=null;
        size=0;
    }
    //链表大小
    public int getSize(){
        return size;
    }
    //头部增加节点
    public void addInHead(Node node){
        if(size==0){
         node.setNext(node);
         head=tail=node;
         size++;
        }else {
            tail.setNext(node);
            node.setNext(head);
            head=node;
            size++;
        }
    }
    //尾部增加节点
    public void addInTail(Node node){
        if(size==0){
            node.setNext(node);
            head=tail=node;
            size++;
        }else {
            tail.setNext(node);
            node.setNext(head);
            tail=node;
            size++;
        }
    }
    //删除头部节点
    public void deleteHead(){
        if(size>1){
            //原来的head=null将会被自动回收
            head=head.getNext();
            tail.setNext(head);
            size--;
        }else if(size==1){
            head=tail=null;
            size--;
        } else {
            System.out.println("链表为空");
        }
    }
    //删除尾部节点
    public void deleteTail(){
        if(size>1){
            Node temp=head;
            //循环遍历找到尾部节点
            while (temp.getNext()!=tail){
                temp=temp.getNext();
            }
            temp.setNext(head);
            size--;
        }else if(size==1){
            head=tail=null;
            size--;
        } else {
            System.out.println("链表为空");
        }
    }
    //遍历节点
    public void traverse(){
        if(size==0)
            System.out.println("链表为空");
        Node temp=head;
        while (temp.getNext()!=head){
            System.out.print(temp.getData());
            System.out.print("--->");
            temp=temp.getNext();
        }
        System.out.print(temp.getData());
        System.out.print("--->");
        System.out.print(head.getData());
    }
}
public class Test {
    public static void main(String[] args) {
        LoopLinkedList list = new LoopLinkedList();
        list.addInHead(new Node(1));
        list.addInHead(new Node(3));
        list.addInHead(new Node(4));
        list.addInTail(new Node(5));
        System.out.println(list.getSize());
        list.traverse();
        System.out.println();
        list.deleteHead();
        list.deleteTail();
        list.traverse();
    }
}
4
4--->3--->1--->5--->4
3--->1--->3

五,链表相关的面试题

求单链表中的有效节点个数

(如果是带头结点的链表,不统计头节点)

/**
	 *
	 * @param head 链表的头节点
	 * @return 返回的就是有效节点的个数
	 */
	public static int getLength(HeroNode head) {
		if(head.next == null) { //空链表
			return 0;
		}
		int length = 0;
		//定义一个辅助的变量, 这里我们没有统计头节点
		HeroNode cur = head.next;
		while(cur != null) {
			length++;
			cur = cur.next; //遍历
		}
		return length;
	}

查找单链表中的倒数第k个结点

思路分析:

1.编写一个方法,接收head节点,同时接收一个indexindex

2.表示是倒数第index个节点

3.先把链表从头到尾遍历,得到链表的总的长度 getLength

4.得到size 后,我们从链表的第一个开始遍历 (size-index)个,就可以得到

5.如果找到了,则返回该节点,否则返回null

public static HeroNode findLastIndexNode(HeroNode head, int index) {
		//判断如果链表为空,返回null
		if(head.next == null) {
			return null;//没有找到
		}
		//第一个遍历得到链表的长度(节点个数)
		int size = getLength(head);
		//第二次遍历  size-index 位置,就是我们倒数的第K个节点
		//先做一个index的校验
		if(index <=0 || index > size) {
			return null;
		}
		//定义给辅助变量, for 循环定位到倒数的index
		HeroNode cur = head.next; //3 // 3 - 1 = 2
		for(int i =0; i< size - index; i++) {
			cur = cur.next;
		}
		return cur;

	}

将单链表反转

如下所示:

思路分析:

代码如下:

public static void reversetList(HeroNode head) {
		//如果当前链表为空,或者只有一个节点,无需反转,直接返回
		if(head.next == null || head.next.next == null) {
			return ;
		}

		//定义一个辅助的指针(变量),帮助我们遍历原来的链表
		HeroNode cur = head.next;
		HeroNode next = null;// 指向当前节点[cur]的下一个节点
		HeroNode reverseHead = new HeroNode(0, "", "");
		//遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead 的最前端
		while(cur != null) {
			next = cur.next;//先暂时保存当前节点的下一个节点,因为后面需要使用
			cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
			reverseHead.next = cur; //将cur 连接到新的链表上
			cur = next;//让cur后移
		}
		//将head.next 指向 reverseHead.next , 实现单链表的反转
		head.next = reverseHead.next;
	}

从尾到头打印链表

方案1.先将链表反转然后打印遍历代码如上所示

方案2.可以利用栈这个数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点,就实现了逆序打印的效果

public static void reversePrint(HeroNode head) {
		if(head.next == null) {
			return;//空链表,不能打印
		}
		//创建一个栈,将各个节点压入栈
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode cur = head.next;
		//将链表的所有节点压入栈
		while(cur != null) {
			stack.push(cur);
			cur = cur.next; //cur后移,这样就可以压入下一个节点
		}
		//将栈中的节点进行打印,pop 出栈
		while (stack.size() > 0) {
			System.out.println(stack.pop()); //stack的特点是先进后出
		}
	}

到此这篇关于Java数据结构之链表详解的文章就介绍到这了,更多相关Java链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • JAVA 数据结构链表操作循环链表

    JAVA 链表操作:循环链表 主要分析示例: 一.单链表循环链表 二.双链表循环链表 其中单链表节点和双链表节点类和接口ICommOperate<T>与上篇一致,这里不在赘述.参考:JAVA链表操作:单链表和双链表http://www.jb51.net/article/95113.htm 一.单链表循环链表 package LinkListTest; import java.util.HashMap; import java.util.Map; public class SingleCycle

  • java实现数据结构单链表示例(java单链表)

    复制代码 代码如下: /** * 单向链表 * */public class NodeList<E> { private static class Node<E> { // 节点类  E data; // 节点上的数据  Node<E> next; // 指向下一个节点 Node(E e) {   this.data = e;   this.next = null;  } } private Node<E> head; // 链表的头节点 private N

  • Java模拟有序链表数据结构的示例

    有序链表: 按关键值排序.删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置. 插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1), 如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择 优先级队列 可以使用有序链表来实现 有序链表的插入排序: 对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2) 复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,

  • Java数据结构之简单链表的定义与实现方法示例

    本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点

  • Java数据结构之双端链表原理与实现方法

    本文实例讲述了Java数据结构之双端链表原理与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.什么时双端链表: 链表中保持这对最后一个连点引用的链表 2.从头部插入 要对链表进行判断,如果为空则设置尾节点为新添加的节点 3.从尾部进行插入 如果链表为空,则直接设置头节点为新添加的节点,否则设置尾节点的后一个节点为新添加的节点 4.从头部删除 判断节点是否有下个节点,如果没有则设置节点为null 二.具体实现 /** * @描述 头尾相接的链表 * @项目名称 Java_DataStr

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • Java描述数据结构学习之链表的增删改查详解

    前言 链表是一种常见的基础数据结构,它是一种线性表,但在内存中它并不是顺序存储的,它是以链式进行存储的,每一个节点里存放的是下一个节点的"指针".在Java中的数据分为引用数据类型和基础数据类型,在Java中不存在指针的概念,但是对于链表而言的指针,指的就是引用数据类型的地址. 链表和数组都是线性的数据结构,对于数组而言其长度是固定的,由于在内存中其是连续的,因此更适合做查找与遍历,而链表在内存中是并不是顺序存储的,但是由于其是通过"指针"构成的,因此在插入.删除时

  • java 数据结构单链表的实现

    java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n

  • java数据结构之实现双向链表的示例

    复制代码 代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{  Node<T> perv;  //前节点  Node<T> next;  //后节点  T data;    //数据 public Node(T t){   this.data = t;  } } priv

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • Java数据结构之链表(动力节点之Java学院整理)

    单链表: insertFirst:在表头插入一个新的链接点,时间复杂度为O(1) deleteFirst:删除表头的链接点,时间复杂度为O(1) find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) public class LinkedList { private class Data{ private Object obj; private Data next =

  • Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1.集合中必存在唯一的一个"第一元素": 2.集合中必存在唯一的一个 "最后元素" : 3.除最后一个元素之外,均有 唯一的后继(后件):

  • java 数据结构之删除链表中的元素实例代码

    java 删除链表中的元素 以下实例演示了使用 Clear() 方法来删除链表中的元素: import java.util.*; public class Main { public static void main(String[] args) { LinkedList<String> lList = new LinkedList<String>(); lList.add("1"); lList.add("8"); lList.add(&q

  • Java 数据结构链表操作实现代码

    链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表.循环链表.双向链表,下面将逐一介绍.链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一.链表的简介 二.链表实现原理和必要性 三.单链表示例 四.双链表示例 一.链表的简介 链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析.链表中数据就像被一个链

  • Java 单链表数据结构的增删改查教程

    我就废话不多说了,大家还是直接看代码吧~ package 链表; /** * *1)单链表的插入.删除.查找操作: * 2)链表中存储的是int类型的数据: **/ public class SinglyLinkedList { private Node head = null; //查找操作 public Node findByValue(int value){ Node p = head; //从链表头部开始查找 while(p.next != null && p.data != va

随机推荐