Elementary List Processing

Kesa...大约 5 分钟algorithmdata structurelinked list

With arrays and structures, we save an item in memory and later refer to it by name (or by index); with linked lists, the manner in which we save information makes it more difficult to access but easier to rearrange.

Working with data that are organized in linked lists is called list processing.

1. Definition

**Definition 3.3 ** A linked list is either a null link or a link to a node that contains an item and a link to a linked list.

This definition is more restrictive than definition 3.2, but it corresponds more closely to the mental model that we have when we write list-processing code.

2. List Processing

2.1 Traverse

One of the common operations that we perform on lists is to traverse them: We scan through the items on the list sequentially, performing some operation on each.

For example, if x is a pointer to the first node of a list, the final node has a null pointer, and visit is a function that takes an item as an argument:

for (t = x; t != NULL; t = t->next) {
    visit(t->item);
}

This loop is as ubiquitous in list-processing programs as is the corresponding for (int i = 0; i < N; i++) in array-processing program.

2.2 List Reversal

Implementation in C :

#include <stdio.h>
#include <stdlib.h>

typedef struct node* Link;
struct node {
    int item;
    Link next;
};

Link reverse(Link head) {
    Link r = NULL;

    for (Link y = head; y != NULL;) {
        // save y to tmp node
        // The variable is allocated once, when the function is called 
        // (https://stackoverflow.com/questions/7959573/declaring-variables-inside-loops-good-practice-or-bad-practice)
        Link tmp = y->next;
        // y point to r(head of reverse list)
        y->next = r;
        // move r to y
        r = y;
        // move y to next
        y = tmp;
    }
    // return the new head of reverse list 
    return r;
}

void print_list(Link head) {
    printf("[");
    for (Link x = head; x != NULL; x = x->next) {
        printf("%d ", x->item);
    }
    printf("]");
}

void print_node(Link node) {
    printf("{item: %d, next: %p", node->item, node->next);
}

void print_list_verbose(Link head) {
    printf("[");
    for (Link x = head; x != NULL; x = x->next) {
        print_node(x);
        printf(", ");
    }
    printf("]");
}

Link new_list(int len) {
    Link head = malloc(sizeof(*head));
    head->item = 0;
    head->next = NULL;

    Link x = head;
    // create a list that item is from 0 to len-1
    for (int i = 1; i < len; i++) {
        Link node = malloc(sizeof(*node));
        node->item = i;

        // add to tail of the lists
        node->next = x->next;
        x->next = node;
        // move x to next
        x = node;
    }
    return head;
}

int main() {
    Link list = new_list(10);
    printf("Before: \n");
    print_list(list);
    printf("\n");
    Link reverseLink = reverse(list);
    printf("\nAfter: \n");    
    print_list(reverseLink);
    printf("\n");
    return 0;
}

Implementation in go:

package main

import (
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Node struct {
	item int
	next *Node
}

func (n *Node) String() string {
	var builder strings.Builder

	builder.WriteString("[")
	for x := n; x != nil; x = x.next {
		builder.WriteString(fmt.Sprintf("%d ", x.item))
	}
	builder.WriteString("]")
	return builder.String()
}

func (n *Node) Reverse() *Node {
	var r *Node
	for x := n; x != nil; {
		t := x.next
		x.next = r
		r = x
		x = t
	}
	return r
}

func NewLinkedList(len int) *Node {
	head := &Node{}

	x := head
	for i := 1; i < len; i++ {
		node := &Node{item: i}

		node.next = x.next
		x.next = node
		x = x.next
	}
	return head
}

func main() {
	if len(os.Args) < 2 {
		fmt.Printf("Usage: ListReversal list_length")
	}
	len, _ := strconv.Atoi(os.Args[1])

	list := NewLinkedList(len)
	fmt.Println(list)
	reverseList := list.Reverse()
	fmt.Println(reverseList)
}

This function reverses the links in a list, returning a pointer to the final node. To accomplish this task, we need to maintain links to three consecutive nodes in the list.

2.3 List Insertion Sort

Clang implementation:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node* Link;
struct Node {
  int item;
  Link next;
};

Link generate_random_list(int len) {
  Link head = malloc(sizeof(*head));
  // head is a dummy node
  Link t = head;
  for (int i = 0; i < len; i++) {
    t->next = malloc(sizeof(*t));
    // move top node to next
    t = t->next;
    t->next = NULL;
    t->item = rand() % 100;
  }
  return head;
}

void print_list(Link head) {
  printf("[");
  // head is a dummy node
  for (Link t = head->next; t != NULL; t = t->next) {
    printf("%d ", t->item);
  }
  printf("]");
}

void print_node_verbose(Link node) {
  printf("{Item: %d, Next: %p}", node->item, node->next);
}

Link insertion_sort(Link inHead) {
  // dummy node
  Link outHead = malloc(sizeof(*outHead));
  outHead->next = NULL;

  // traverse input list
  for (Link x = inHead->next; x != NULL;) {
    Link tmp = x->next;
    Link y;
    for (y = outHead; y->next != NULL; y = y->next) {
      if (x->item < y->next->item) {
        break;
      }
    }
    x->next = y->next;
    y->next = x;
    x = tmp;
  }
  // inHead is no longer to use
  // release memory
  free(inHead);
  return outHead;
}

int main(int argc, char* argv[]) {
  if (argc < 2) {
    printf("Usage: ListInsertion list_length");
    return 1;
  }
  Link list = generate_random_list(atoi(argv[1]));
  print_list(list);
  printf("\n");
  Link sortedList = insertion_sort(list);
  print_list(sortedList);
  return 0;
}

Golang implementation:

package main

import (
	"fmt"
	"math/rand"
	"os"
	"strconv"
	"strings"
)

type Node struct {
	item int
	next *Node
}

func (n *Node) InsertionSort() *Node {
	sortedHead := &Node{}

	for x := n.next; x != nil; {
		tmp := x.next
		var y *Node
		for y = sortedHead; y.next != nil; y = y.next {
			if x.item < y.next.item {
				break
			}
		}
		x.next = y.next
		y.next = x
		x = tmp
	}
	return sortedHead
}

func (n Node) String() string {
	var builder strings.Builder

	builder.WriteString("[")
	for x := n.next; x != nil; x = x.next {
		builder.WriteString(fmt.Sprintf("%d ", x.item))
	}
	builder.WriteString("]")

	return builder.String()
}

func NewRandomList(len int) *Node {
	head := &Node{}
	t := head
	for i := 0; i < len; i++ {
		n := &Node{item: rand.Intn(100)}
		t.next = n
		t = t.next
	}

	return head
}

func main() {
	if len(os.Args) < 2 {
		fmt.Println("Usage ListInsertionSort list_length")
	}
	len, _ := strconv.Atoi(os.Args[1])

	list := NewRandomList(len)
	fmt.Println(list)
	sortedList := list.InsertionSort()
	fmt.Println(sortedList)
}

We maintain a dummy node called a head node at the beginning of each list. We ignored the item field in a list’s head node, but maintain its link as the pointer to the node containing the first item in the list.

The program uses two lists:

  • One to collect the random input in the first loop
  • Another to collect the sorted output in the second loop

The primary reason to use the head node at the beginning becomes clear when we consider the process of adding the first node to the sorted list.

We have three options:

  1. Duplicate the for loop that finds the smallest item and set up a one-node list.

  2. Test whether the output list is empty every time that we wish to insert a node.

  3. Use a dummy head node whose link points to the first node on the list.

The first option is inelegant and requires extra code; the second is also inelegant and requires extra time.

3. Head and tail conventions in linked lists

3.1 Circular, never empty

OperationCode
fist inserthead->next = head;
insert t after xt->next = x->next; x->next = t;
delete after xx->next = x->next->next;
traversal loopt = head; do {... t = t->next; } while (t != head);
test if one itemif (head->next) == head

3.2 Head pointer, null tail

OperationCode
initializehead = NULL
insert t after xif (x == NULL){head = t; head->next = NULL;}
else {t->next = x->next; x->next = t;}
delete after xt = x->next; x->next = t->next;
traversal loopfor (t = head; t != NULL; t=t->next)
test if emptyif (head == NULL)

3.3 Dummy head node, null tail

OperationCode
initializehead = malloc(sizeof *head);
head->next = NULL;
insert t after xt->next = x->next; x->next = t;
delete after xt = x->next; x->next = t->next;
traversal loopfor (t = head->next; t != NULL; t = t->next)
test if emptyif (head->next == NULL)

3.4 Dummy head and tail nodes

OperationCode
initializehead = malloc(sizeof *head);
z = malloc(sizeof *z)
head->next = z; z->next = z;
insert t after xt->next = x->next; x->next = t;
delete after xt = x->next; x->next = t->next;
traversal loopfor (t = head->next; t != z; t = t->next)
test if emptyif (head->next == z)

Reference

  1. Algorithms in Copen in new window
上次编辑于:
0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.15.2