链表

单链表定义和表示

  • 线性表的链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素(逻辑上相邻,物理上可以不相邻)。
  • 结点:为了表示数据a(i)和其直接后继a(i+1)的逻辑关系的存储映像,它包含两个域:存储数据元素的“数据域”和存储直接后继存储位置的域“指针域”,指针域中存储的信息称为指针或链。
  • 单链表:n个节点链结成一个链接即为线性表的链式存储结构。由于链表每个结点只包含一个指针域,又称线性链表或者单链表。

根据链表结点指针个数,指向和连接方式,可将链表分为单链表、循环链表、双向链表、二叉链表,十字链表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构,其他形式多用于实现树和图等非线性结构。

单链表的基本操作和实现

单链表的计算长度和获取值域

计算链表长度

public int size() {
        SingleNode<E> cur = HEAD_NODE;
        int length = 0;
        while (cur.next != null) {
            ++length;
            cur = cur.next;
        }
        return length;
    }

获取对应位置的值域

public E get(int index) {
        if (index < 0) {
            throw new RuntimeException("index 不能小于0");
        }
        int length = size();
        if (index > length) {
            throw new RuntimeException("链表长度为" + length + ",可选择位置0-" + (length - 1) + ";当前选择位置是:" + index);
        }
        SingleNode<E> cur = HEAD_NODE;
        int p = 0;
        while (cur.next != null && p <= index) {
            cur = cur.next;
            ++p;
        }
        return cur.value;
    }

单链表的插入节点

在某个链表,第n个位置,添加一个某数值e的新结点,即添加此结点到n-1和n位置之间

  1. 找到节点a(n-1)
  2. 生成一个新结点
  3. 将新结点值域设置为e
  4. 将新结点指针域指向节点a(n)
  5. 将a(n-1)结点指针域指向新结点

代码如下所示:

//在链表最后添加值
public void add(E e) {
        SingleNode<E> cur = HEAD_NODE;
        //找到最后一个结点
        while (cur.next != null) {
            cur = cur.next;
        }
        //新建结点,设置值域
        SingleNode<E> node = new SingleNode<>(e);
        //在最后添加新的结点
        cur.next = node;
}
//在某个节点添加新数值
public void add(int index, E e) {
        if (index < 0) {
            throw new RuntimeException("index 不能小于0");
        }
        int length = size();
        if (index > length) {
            throw new RuntimeException("链表长度为" + length + ",可选择插入位置0-" + length + ";当前选择插入位置是:" + index);
        }
        int p = 0;
        //HEAD_NODE 为头结点,HEAD_NODE.next 即为0号位置引用
        SingleNode<E> cur = HEAD_NODE;
        while (cur.next != null && p <= (index - 1)) {
            ++p;
            cur = cur.next;
        }
        //新建结点,通过构造设置值域
        SingleNode<E> node = new SingleNode<>(e);
        node.next = cur.next;
        cur.next = node;
    }

单链表的删除节点

在一个链表中删除n号元素位置的结点,和插入结点差不多

  1. 找到a(n-1)结点
  2. 将a(n-1)结点指针域指向a(n)的直接后继结点

代码如下所示:

//根据下标索引删除
public void delete(int index) {
        if (index < 0) {
            throw new RuntimeException("index 不能小于0");
        }
        int length = size();
        if (index > length - 1) {
            throw new RuntimeException("链表长度为" + length + ",可选择删除的位置0-" + (length - 1) + ";当前选择删除的位置是:" + index);
        }
        int p = 0;
        SingleNode<E> cur = HEAD_NODE;
        //找到目标结点的前驱结点
        while (cur.next != null && p <= (index - 1)) {
            ++p;
            cur = cur.next;
        }
        if (cur.next != null) {
            cur.next = cur.next.next;
        }
}
//删除值
public void delete(E e) {
        SingleNode<E> cur = HEAD_NODE;
        while (cur.next != null) {
            if (e.equals(cur.next.value)) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
}

前插法创建单链表

前插法创建单链表,每次将新结点逐个插入链表头部,所以线性表(a、b、c、d、e、f、g)前插法创建,读入数据的顺序和线性表的逻辑顺序是相反的

  1. 创建头结点
  2. 创建新结点,设置值域
  3. 将新结点插入表头
//main函数,插入数据创建链表
public static void main(String[] args) throws Exception {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.createFront("g", "f", "e", "d", "c", "b", "a");
        //linkedList.createFront1("a","b","c","d","e","f","g");
        linkedList.printSelf();
    }
//前插法创建单链表
public void createFront(E... values) {
        for (int i = 0; i < values.length; i++) {
            SingleNode<E> node = new SingleNode<>();
            node.value = values[i];
            node.next = HEAD_NODE.next;
            HEAD_NODE.next = node;
        }
    }
//或者为了使用方便,可以这么写
public void createFront1(E... values) {
        for (int i = values.length - 1; i >= 0; i--) {
            SingleNode<E> node = new SingleNode<>();
            node.value = values[i];
            node.next = HEAD_NODE.next;
            HEAD_NODE.next = node;
        }
    }
打印结果

后插法创建单链表

后插法是将新结点逐个插入到链表的尾部来创建链表

  1. 创建一个只有头结点的空链表
  2. 新增一个尾指针结点r
  3. 将新结点插入尾结点r之后,再使r指向新的 尾结点
//main函数,创建链表
public static void main(String[] args) throws Exception {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.createLater("a", "b", "c", "d", "e", "f", "g");
        linkedList.printSelf();
    }
//后插法创建链表
public void createLater(E... values) {
        SingleNode<E> r = HEAD_NODE;
        for (int i = 0; i < values.length; i++) {
            SingleNode<E> node = new SingleNode<>();
            node.value = values[i];
            node.next = null;
            r.next = node;
            r = node;
        }
    }
打印结果

循环链表

循环链表是另外一种形式的链式存储结构。最明显的特征就是,尾结点指针域指向头结点,整个链表形成一个环。因此,从表中任一结点出发均可找到表中其他节点。如下图所示。类似的还有多重链的循环链表。


循环链表

双向链表

单链表只有一个指示直接后继的指针域,因此,从某个结点出发只能顺时针向后查询其他节点,如果需要查询直接前驱,则必须从表头指针出发。为了克服单链表这种单向性的缺点,可以利用双向链表。
顾名思义,在双向链表中有两个指针域,一个指向直接后继,一个指向直接前驱,结点结构如下图所示。代码可以如下描述:


双向链表结点图示
public class DoubleLinkList<T> {
    private Node<T> HEAD_NODE;

    public DoubleLinkList() {
        this.HEAD_NODE = new Node<>();
    }
    //结点实体类
    class Node<T>{
        Node<T> prior;
        Node<T> next;
        T data;
    }
}

和单链表类似,双向链表也可以有循环表,如下图所示:

非空的双向循环链表

其实能熟练掌握单链表的结构和操作,就能够很快熟悉理解双向链表。比如单链表插入一个新结点到指定结点(p)之后需要三步:1. 找到目标位置;2. 新结点的指针域指向目标结点p的直接后继;3. 目标结点p指针域指向新结点即可。双向链表中,每个结点要多出一个指针域,所以在插入和删除的时候需要多处理一个指针域,原理都是一样的,如下做了双向链表的插入和删除操作

双向链表的插入

双向链表插入结点逻辑示意图

如上图链表中有A、B、C三个结点(头结点忽略)。要在A和B之间插入新结点F(即在1号位置插入),则需要以下4步

  1. 找到A结点(0号位置)
  2. 新结点的两个指针分别指向A和B
  3. B的前驱结点的指针指向新结点
  4. A的后继的指针指向新结点
    //插入链表指定位置
    public void add(int position, T t) {
        //计数器,记录当前位置
        int index = 0;
        Node<T> curNode = HEAD_NODE;
        //定位到目标位置的前驱结点,头结点不计算在内
        do {
            //指定插入位置在当前链表中存在(逻辑上允许插入到链表最后一个结点后)
            if (index == position) {
                break;
            }
            ++index;
            curNode = curNode.next;
        } while (curNode.next != null);
        if (position == index) {
            Node<T> node = new Node<>();
            //指定新结点的值域和两个指针域
            node.data = t;
            node.prior = curNode;
            node.next = curNode.next;
            if (curNode.next != null) {
                //当前结点如果有直接后继,将后继结点的前驱指针指向新结点
                curNode.next.prior = node;
            }
            //当前结点后继的指针指向新结点
            curNode.next = node;
            return;
        }
        System.out.println("插入失败,指定的位置不存在");
    }

双向链表的删除

理解如何添加一个结点之后,举一反三,删除就很好理解了,如下图如果要删除B结点,则需要A结点后继指针指向C,C结点的前驱指针指向A即可。


删除B结点逻辑示意图
 public void delete(int position) {
        //计数器,记录当前位置
        Node<T> curNode = HEAD_NODE;
        //找到当前位置的结点
        for (int i = 0; i <= position; i++) {
            curNode = curNode.next;
            if (curNode == null) {
                break;
            }
        }
        if (curNode == null || position < 0) {
            System.out.println("删除失败,指定的位置不存在");
            return;
        }
        if (curNode.next != null) {
            curNode.next.prior = curNode.prior;
        }
        curNode.prior.next = curNode.next;
        curNode.next = null;
        curNode.prior = null;
    }

链表常见操作

反转单链表

顾名思义,就是将一个单链表头结点指向尾结点,原来的直接后继变成了直接前驱,方法有很多,比如new 一个新的链表,然后插入;还可以在当前链表直接操作,下面举的例子就是在当前链表直接进行反转,代码和示意图如下所示:


反转单链表
//反转链表方法
public void reverseList() {
        //链表第一个结点,翻转后成为尾结点,指针域为null
        SingleNode<E> p = HEAD_NODE.next;
        SingleNode<E> pCur = p.next;
        while (pCur != null) {
            p.next = pCur.next;
            pCur.next = HEAD_NODE.next;
            HEAD_NODE.next = pCur;
            pCur = p.next;
        }
    }
打印效果
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,001评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,210评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,874评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,001评论 1 291
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,022评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,005评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,929评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,742评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,193评论 1 309
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,427评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,583评论 1 346
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,305评论 5 342
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,911评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,564评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,731评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,581评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,478评论 2 352

推荐阅读更多精彩内容