黑马程序员技术交流社区

标题: 关于链表的疑惑？ [打印本页]

---

作者: 蔡陶军    时间: 2013-3-21 23:18
标题: 关于链表的疑惑？


哪位大神能帮我详细分析讲解一下，关于链表的增删改查的操作是怎么进行的。今天刚看了些资料，没啥思路，云里雾里。Thank you very much!!!

---

作者: 谢洋    时间: 2013-3-21 23:48


按我的理解来说吧：链表跟现实中的链表很大的相似之处；
通常我们在描述链表的时，都用节点这个词来形容一个元素与下一个元素的联系，现实中如铁链也一节一节，上一节链着下一节。
链表的节点是怎么样的？节点上有某个元素及下一或上一个元素的的地址这些内容，比如需要对某个元素查找，可通过从当前节点获取上一个或下一个元素的地址,这样就可找到上一个或下一个元素了,逐个查找；
为什么链表结构的增删比数组结构速度要快？
从上链表结构原理来看，当要删除一个节点(元素)时，只要把被删节的前一个节点指向下一个节点的地址修改为指向被删节点的后一个节点就可以了，
而数组则不同，他除了找到元素删除后需对组的长度，角标等信息进行一系例的操作,这里比较复杂，我也不知具体怎么实现的.
相反，查找组数据构相对较快，特别是元素很多的时候较为明显，为什么不用多说了吧，链表是一个个的查，而数组可以根据角标来查。

---

作者: 王_强    时间: 2013-3-22 10:07
关于链表的使用：
首先，它是一种数据结构，也就是反应各个数据内部联系的一种方法。
其次，既然是数据结构，我们一般可以在java.util包中去查看api文档。

其实，链表的使用比较的简单，你要和数组结合起来看，就会明白他们各自有什么优势：
链表的增删改查（相比 数组）：
查找、改速度慢：因为要一个一个从第一元素开始，知道找到目标位置，但是数组不同，它有下标来直接查找。
增删： 这个比数组效率要高，因为数组要涉及到移动数据，但是链表不需要，只要更改下相邻的节点指针即可。

其实，链表就是一个个节点用指针连接起来的，明白了这点，我相信你就会懂了，在下次使用数据结构选择时，我们更加数据的事增删操作多谢，还是改查多谢，
我们就可以选择适当的数据结构了！
希望这些能帮助你！

---

作者: qintoko    时间: 2013-3-22 10:14
简单总结一下
1　常见数据结构有哪些
　栈、队列、数组、链表

2　栈（Last In First Out）
后进先出，最上面的元素我们叫栈顶元素！
出栈（弹栈），就是把栈顶元素从栈中移除，并返回。
压栈，就是把一个新元素放到栈顶位置。

3　队列（FIFO）
先进先出！
没底的管道！

4　数组
数组索引元素的速度天下无敌！
arr[10] – 快速最快！
如果我们需要向数组插入和删除元素，那么就需要copy数组。

5　链表
链表元素在内存中不是邻居，链表头元素知道下一个元素的地址，下一个元素又知道下下元素的地址，最后一个元素，即链表尾，它的下一个元素是null。
链表的索引速度很慢，但插入和删除元素快速很快。

---

作者: strawberry2013    时间: 2013-3-22 11:00
public class LinkTest
{
    public static void main(String args[])
    {
        Node head=new Node("head");//头节点
        Node one=new Node("唐僧");//首节点
        Node two=new Node("孙悟空");
        Node three=new Node("猪八戒");
        Node four=new Node("沙和尚");
      
        Link link=new Link(head);
        link.addNode(one);//在尾部添加节点
        link.addNode(two);
        link.addNode(three);
        link.addNode(four);
        link.display();//遍历链表
        System.out.println("-------------------------添加other");
        Node other=new Node("other");
        link.insertNode(two,other);//插入一个节点
        link.display();
        System.out.println("-------------------------删除other");
        link.delNode("other");//删除节点
        link.display();
    }
}
/**
*封装了对节点的一些操作
*
*/
class Link
{
    private Node head;
    public Link(Node head)
    {
        this.head=head;
    }
    public void addNode(Node node)
    {
        Node p=head;
        while(true)
        {
            if(!p.hasNext())
            {
                p.setNext(node);
                break;
            }
            p=p.getNext();
        }
    }
    //插入节点
    public void insertNode(Node p,Node q)
    {
        q.setNext(p.getNext());
        p.setNext(q);
    }
    //删除节点
    public boolean delNode(String nodeName)
    {
        Node p=head;
        if(!p.hasNext())
        {
            System.out.println("此表为空");
            return false;
        }
        while(p.hasNext())
        {
            if(p.getNext().getName().equals(nodeName))
            {
                p.setNext(p.getNext().getNext());
                break;
            }
            p=p.getNext();
        }
        return true;
    }
    //遍历链表
    public void display()
    {
        Node p=head.getNext();
        while(p.hasNext())
        {
            System.out.println(p.getName());
            p=p.getNext();
        }
    }
}
/**
*节点封装类
*
*
*/
class Node
{
    private String nodeName;
    private Node next;
    //用数据域构造一个节点对象
    public Node(String nodeName)
    {
        this.nodeName=nodeName;
    }
    //返回下一节点的对象
    public Node getNext()
    {
        return this.next;
    }
    //设置本节点的链域
    public void setNext(Node next)
    {
        this.next=next;
    }
    //返回节点的数据域
    public String getName()
    {
        return this.nodeName;
    }
    //判断是否有下一节点
    public boolean hasNext()
    {
        boolean is=false;
        if(this.next!=null)
        {
            is=true;
        }
        return is;
    }
}

---

作者: 张文星    时间: 2013-3-22 11:03

这是一个链表的示意图，对于单向链表来说，每个节点都有两部分组成，第一部分为元素内容，第二部分为存储下一节点的引用，或者说是在内存中的地址吧，以此来将不在连续存储区的内容链接起来，最后一个元素的指向下一个元素引用为空，程序中以next是否为空来判断是否到达末尾，所以说，对链表的插入删除等要比数组操作简单的多，执行插入操作时，如上面在a,b之间插入f，只需要将a节点指向下一个节点的引用换成f的,f 的指向下一个节点的内容换成b的引用就好了，删除就更简单了，如删除b节点，只需将a节点中存下一个节点的引用换成c的就好了，对于双向链表，只需多一个存储上一节点的内容就好了

---

作者: 陈志强    时间: 2013-3-22 16:02
在毕老师的视频里是这样讲的，链表数据结构很像我们现实生活中的链子一样，一个节点一个节点的链接在一起，这个时候我们想要去查找链表数据 里的某一个元素时，就像我们在找链子的某一个节点一样，对于元素的查找是要一个一个节点的查找下去，那么查询的动作就显得有些慢了，因为要找到这个元素的话，就要先问过在这个节点之前的元素。
那么增删是什么样子的呢？
也就是说它想要增加一个节点的话，就是在这两个元素之间添加一个元素，只是改变这个链子锁连接的结构，让前一个元素不在记住原来后一个元素而是记住这个新增的节点，这样就实现了增加，同时删除也是，就是让前后两个节点不再记住这个元素，而是相互连接前后的节点就可以了。
希望对你有所帮助

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2