java单链表使用总结

java单链表使用总结

链表的概念:

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

链表的优势

不需要知道数据的大小，可以充分利用计算机内存空间，实现灵活的内存动态管理链表允许插入和移除表上任意位置上的节点(但是不允许随机存取)

链表的缺点

不能像数组一样随机读取增加了空间的开销(增加了节点的指针域)

代码实现

定义一个节点类

public class ListNode {//定义节点类

int val;

ListNode next;

ListNode(int x) {

val = x;

}

//将数组的值赋给链表

public ListNode getList(int[] sums) {

ListNode dummyHead = new ListNode(0);

ListNode curr = dummyHead;

for (int i = 0; i < sums.length; i++) {

curr.next = new ListNode(sums[i]);

curr = curr.next;

}

return dummyHead.next;

}

//将链表的值赋给list并打印

public void showList(ListNode listNode) {

List list = new ArrayList();

while (listNode != null) {

list.add(listNode.val);

listNode = listNode.next;

}

for (int i = 0; i < list.size(); i++) {

System.out.println(list.get(i));

}

}

/**

* leetcode第二题

*

* 给出两个非空的链表用来表示两个非负的整数，

* 其中，它们各自的位数是按照逆序的方式存储的，

* 并且它们的每一个节点只能存储一位数组。

* @param l1

* @param l2

* @return

*/

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode dummyHead = new ListNode(0);

ListNode p = l1, q = l2, curr = dummyHead;

int carry = 0;

while (p != null || http://q != null) {

int x = (p != null) ? p.val : 0;

int y = (q != null) ? q.val : 0;

int sum = carry + x + y;

carry = sum / 10;

curr.next = new ListNode(sum % 10);

curr = curr.next;

if (p != null) p = p.next;

if (q != null) q = q.next;

}

if (carry > 0) {

curr.next = new ListNode(carry);

}

return dummyHead.next;

}

}

测试方法

public class main {

public static void main(String[] args) {

int a[] = {2, 4, 3};

int b[] = {5, 6, 4};

ListNode curr=new ListNode(0);

ListNode l1=curr.getList(a);

// curr.showList(l1);

ListNode l2=curr.getList(b);

// curr.showList(l2);

ListNode l3=curr.addTwoNumbers(l1,l2);

curr.showList(l3);

}

}

输入[2,4,3],[5,6,4]

输出[7,0,8]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。